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:


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 {

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) {
            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;
            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);

        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]);
        if (graph.hasTerminal(operators[1])) {
            this.second = graph.getTerminal(operators[1]);
        } else {
            this.second = new Terminal(operators[1]);

    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));
                case "/":
                    result.setValue(String.valueOf(firstValue / secondValue));
        }catch (Exception e){
            System.out.println(String.format("Exception while executing this: %s",this ));

    boolean conflictWith(Nonterminal nonterminal){
            return true;
        for(Terminal input : getInputs()){
                return true;
        for(Terminal input : nonterminal.getInputs()){
                return true;
        return false;

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

    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);

        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)) {
            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<>();

            for(Nonterminal candidate : candidates){
                        .noneMatch(passedCandidate -> passedCandidate.conflictWith(candidate))){

        // 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));

        for(List<Node> level : program){
            for(Node node : level){
            for(Node node : level){


        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 -> terminal.getLabel().equals(content));

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

    void addTerminal(Terminal 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);

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 *