Skip to content

Maximal parallel system

This is my solution for the lecture “System programming and operating system”.  Following is the problem:

Given the following commands, which should be executed sequentially. Please design a maximal parallel system,  which execute the commands as parallel as possible:

d=2*2;
x=2*25;
g=d*3;
b=8*5;
a=x*2;
y=b*3;
h=d*5;
z=2*5;
i=g*h;
u=y*z;
v=a*i;
c=v/u;

To make the input more simple, we can name each operation with a pseudo name like the following:

t1 = d=2*2;
t2 = x=2*25;
t3 = g=d*3;
t4 = b=8*5;
t5 = a=x*2;
t6 = y=b*3;
t7 = h=d*5;
t8 = z=2*5;
t9 = i=g*h;
t10 = u=y*z;
t11 = v=a*i;
t12 = c=v/u;

For this problem, I chose Java as my tool, since Java’s API has an excellent implementation of multithreading. My idea is to implement a graph, which consists of nodes. Each of those nodes will execute an operation completely independently from other nodes, the final result of c=v/u should be deterministic.

First of all, we need to design the problem in an object-oriented way. Each of the operations will be called non-terminal while each variable, constant or operation will be called terminal.

A terminal could be a variable, a constant or an operation. This could be done with a plain old Java enum:

public enum TerminalType {
    CONST,
    OPERATOR,
    VARIABLE
}

The Terminal otherwise will have a value, a label, and a terminal type. The terminal type of a terminal is immutable, the label is also not changeable after being assigned. The value, however, will be changed after the execution of each non-terminal.

import java.util.Objects;

public class Terminal {
    private TerminalType terminalType;
    private volatile String value;
    private String label;

    Terminal(final String content) {
        if(content.matches("[a-z]")){
            this.terminalType = TerminalType.VARIABLE;
            this.value = "0";
            this.label = content;
        }else if(content.matches("[0-9]+")){
            this.terminalType = TerminalType.CONST;
            this.value = content;
            this.label = content;
        }else if(content.equals("/") || content.equals("*")){
            this.terminalType = TerminalType.OPERATOR;
            this.value = content;
            this.label = content;
        }else{
            throw new RuntimeException(String.format("Invalid content: %s", content));
        }
    }
}

In the only constructor of a terminal, we will assign its terminal type according to the string parameter. If the parameter is an alphabet, it shall be a variable, otherwise, it could be an operation or a constant. Speaking of operations we will only support division and multiplication since the homework itself doesn’t contain more operations.

Coming to non-terminal, a non-terminal is, for example, the expression c=v/u, which consists of a result, two operators and an operation type. Since we want the terminals to be unique and be shared between non-terminals, we want to create a set which will return a terminal, if it already exists. This could be achieved with another class we shall call Graph. The graph will be given while constructing a non-terminal object. Moreover, we want to evaluate a non-terminal with the method execute(), which will basically evaluate the result of the equation. In order to have the result deterministic, we need to execute every non-terminal in a very specific order. This order will be set inside a Graph.

A non-terminal is also in conflict with another non-terminal if both of them somehow need access to one same terminal.

public class Nonterminal {
    private Terminal result;
    private Terminal first;
    private Terminal operation;
    private Terminal second;

    Nonterminal(final String content, final Graph graph) {
        String[] tokens = content.split("=");
        String result = tokens[0];
        String equation = tokens[1];

        if (graph.hasTerminal(result)) {
            this.result = graph.getTerminal(result);
        } else {
            this.result = new Terminal(result);
            graph.addTerminal(this.result);
        }

        String[] operators;
        if (equation.contains("*")) {
            operation = new Terminal("*");
            operators = equation.split("\\*");
        } else if (equation.contains("/")) {
            operation = new Terminal("/");
            operators = equation.split("/");
        } else {
            throw new RuntimeException("WTF?");
        }

        if (graph.hasTerminal(operators[0])) {
            this.first = graph.getTerminal(operators[0]);
        } else {
            this.first = new Terminal(operators[0]);
            graph.addTerminal(first);
        }
        if (graph.hasTerminal(operators[1])) {
            this.second = graph.getTerminal(operators[1]);
        } else {
            this.second = new Terminal(operators[1]);
            graph.addTerminal(second);
        }
    }

    void execute() {
        long firstValue = Long.parseLong(first.getValue());
        long secondValue = Long.parseLong(second.getValue());
        try {
            switch (operation.getValue()) {
                case "*":
                    result.setValue(String.valueOf(firstValue * secondValue));
                    break;
                case "/":
                    result.setValue(String.valueOf(firstValue / secondValue));
                    break;
                default:
                    break;
            }
        }catch (Exception e){
            System.out.println(String.format("Exception while executing this: %s",this ));
        }
    }

    boolean conflictWith(Nonterminal nonterminal){
        if(this.getOutput().equals(nonterminal.getOutput())){
            return true;
        }
        for(Terminal input : getInputs()){
            if(input.equals(nonterminal.getOutput())){
                return true;
            }
        }
        for(Terminal input : nonterminal.getInputs()){
            if(input.equals(this.getOutput())){
                return true;
            }
        }
        return false;
    }

    private List<Terminal> getInputs() {
        return Stream.of(first, second)
                .filter(terminal -> terminal.getTerminalType().equals(TerminalType.VARIABLE))
                .collect(Collectors.toList());
    }

    private Terminal getOutput() {
        return result;
    }

    String getResult(){
        return result.getValue();
    }
}

Finally, we will take a look at the most important class of this problem, the graph. A graph will take an input string, tokenize the input and evaluate its meaning. Each created non-terminal will then be assigned with a Node, which is a subclass of the Java’s Thread class. The node will execute the non-terminal completely independently from every other node

The algorithm itself is very simple:

  • First of all, create a permutation for every two-non-terminal combination. (t1t2, t1t3, t1t4, etc…)
  • A permutation is invalid if its components have access to the same terminal.
  • The permutations will be laid into layers.
  • Iterate each layer, conflicting terminals will once again be resolved by removing one of the conflict parties.
  • Execute the graph.
import java.util.*;

class Graph {
    private Set<Nonterminal> nonTerminals = new LinkedHashSet<>();
    private Set<Terminal> terminals = new LinkedHashSet<>();
    private Nonterminal lastNonTerminal;

    Graph(final String input) {
        if (!input.endsWith(";")) {
            throw new RuntimeException("Invalid syntax");
        }
        final String noEmptyInput = input.replace(" ", "");

        final String removedLastSemicolon = noEmptyInput.substring(0, noEmptyInput.length() - 1);

        final String[] tokens = removedLastSemicolon.split(";");
        for(int i = 0; i < tokens.length - 1; i++){
            String token = tokens[i];
            Nonterminal nonterminal = new Nonterminal(token, this);
            this.nonTerminals.add(nonterminal);
        }

        lastNonTerminal = new Nonterminal(tokens[tokens.length - 1], this);
    }

    void execute() throws InterruptedException {
        // First filter
        // Filter out every non-terminal that conflicts with the primary non-terminal
        Map<Nonterminal, List<Nonterminal>> firstRoundFilter = new LinkedHashMap<>();

        for(Nonterminal primary : nonTerminals){
            List<Nonterminal> noConflicts = new ArrayList<>();
            for(Nonterminal second : nonTerminals){
                if(primary != second){
                    if(!primary.conflictWith(second)) {
                        noConflicts.add(second);
                    }
                }
            }
            firstRoundFilter.put(primary, noConflicts);
        }

        // Second filter
        // Filter out every non-terminal that conflicts with other in the primary non-terminal
        List<List<Nonterminal>> executions = new ArrayList<>();

        for(Nonterminal primary : firstRoundFilter.keySet()){
            List<Nonterminal> candidates = firstRoundFilter.get(primary);
            List<Nonterminal> noConflicts = new ArrayList<>();
            noConflicts.add(primary);

            for(Nonterminal candidate : candidates){
                if(noConflicts
                        .stream()
                        .noneMatch(passedCandidate -> passedCandidate.conflictWith(candidate))){
                    noConflicts.add(candidate);
                }
            }
            executions.add(noConflicts);
        }

        // Convert to programm
        List<List<Node>> program = new ArrayList<>();
        for(List<Nonterminal> nonterminals : executions){
            List<Node> programLevel = new ArrayList<>();
            for(Nonterminal nonterminal : nonterminals){
                programLevel.add(new Node(nonterminal));
            }
            program.add(programLevel);
        }

        for(List<Node> level : program){
            for(Node node : level){
                node.start();
            }
            for(Node node : level){
                node.join();
            }
        }

        lastNonTerminal.execute();

        for(Nonterminal nonterminal : nonTerminals){
            System.out.println(String.format("Terminal: %s has result %s", nonterminal, nonterminal.getResult()));
        }
        System.out.println(String.format("Terminal: %s has result %s", lastNonTerminal, lastNonTerminal.getResult()));
    }

    boolean hasTerminal(String content) {
        return terminals.stream().anyMatch(terminal -> terminal.getLabel().equals(content));
    }

    Terminal getTerminal(String content) {
        Optional<Terminal> found =
                terminals.stream().filter(terminal -> terminal.getLabel().equals(content)).findFirst();
        return found.orElse(null);
    }

    void addTerminal(Terminal terminal) {
        terminals.add(terminal);
    }
}

Executing the graph with the following code:

public class Main {
    public static void main(String[] args) throws InterruptedException {
        final String input = "d=2*2;x=2*25;g=d*3;b=8*5;a=x*2;y=b*3;h=d*5;z=2*5;i=g*h;u=y*z;v=a*i;c=v/u;";
        Graph graph = new Graph(input);
        graph.execute();
    }
}

will result in the following output:

Terminal: NonTerminal{Terminal{d} = Terminal{2} Terminal{*} TERMINAL{2}} has result 4
Terminal: NonTerminal{Terminal{x} = Terminal{2} Terminal{*} TERMINAL{25}} has result 50
Terminal: NonTerminal{Terminal{g} = Terminal{d} Terminal{*} TERMINAL{3}} has result 12
Terminal: NonTerminal{Terminal{b} = Terminal{8} Terminal{*} TERMINAL{5}} has result 40
Terminal: NonTerminal{Terminal{a} = Terminal{x} Terminal{*} TERMINAL{2}} has result 100
Terminal: NonTerminal{Terminal{y} = Terminal{b} Terminal{*} TERMINAL{3}} has result 120
Terminal: NonTerminal{Terminal{h} = Terminal{d} Terminal{*} TERMINAL{5}} has result 20
Terminal: NonTerminal{Terminal{z} = Terminal{2} Terminal{*} TERMINAL{5}} has result 10
Terminal: NonTerminal{Terminal{i} = Terminal{g} Terminal{*} TERMINAL{H}} has result 240
Terminal: NonTerminal{Terminal{u} = Terminal{y} Terminal{*} TERMINAL{Z}} has result 1200
Terminal: NonTerminal{Terminal{v} = Terminal{a} Terminal{*} TERMINAL{I}} has result 24000
Terminal: NonTerminal{Terminal{c} = Terminal{v} Terminal{/} TERMINAL{U}} has result 20

 

Published inSoftware Engineer

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *