Programming Model

This page describes the reasons for the chosen programing model and the consequences thereof.

The main goal of the library is to provide a convenient api for solving problems parallel without the need for a deep understanding of underlining the und technologies or paradigms. Parallelizing the problems can be used to reduce the needed time to solve the problem or improving the user experience.

Reactive vs Imperative

The used api is reactive, compared to other libraries that are mostly imperative (e.g. thread.js). The main disadvantage of a reactive api is its non intuitive usage in an imperative language like JavaScript. Therefore, it might require some unusable approaches to solve certain problems or might not be suited to solve some problems after all. However, a reactive api has been chosen for the following reasons

• Intelligent API: A reactive api adds additional information to the runtime of what the user wants to achieve. This additional knowledge can be used to automatically parallelize a problem without additional work of the user. However, the api should allow the user to perform fine tuning - for cases where the heuristic fails or does not perform optimal. In a pure imperative API, parallelization needs to be explicitly performed by the user and is therefore less convenient.
• Static Analyzable: The API should contain enough information to allow static analysis and code rewriting to overcome the many restriction caused by the serialization of functions (debugging support, access to closure). Identifying potentially parallel code in an imperative environment is far more complicated.

Joining

Recursion

Recursion can be supported by providing an expand(enter, exit) method. The expand method is called for every element and returns an array. The method is then called again for each element it has returned.

parallel
    .single({ coordinate: { x: 0, y: 0 }, n: 1 })
    .expand(function ({ coordinate, n }, environment) {
        if (n === environment.numberOfFields) { // base case
            return [];
        }

        const fieldIndex = coordinate.x * environment.boardSize + coordinate.y;
        environment.board[fieldIndex] = n;
       
        const result = []; 
        for (const move of moves) {
            const successor = { x: coordinate.x + move.x, y: coordinate.y + move.y };
            // not outside of board and not yet accessed
            const accessible = successor.x >= 0 && successor.y >= 0 && successor.x < boardSize &&  successor.y < boardSize && board[successor.x * boardSize + successor.y] === 0;

            if (accessible) {
                result.push({ coordinate: successor, n: n + 1 });
            }
        }
        return result;
    }, function ({ coordinate }) {
        environment.board[fieldIndex] = 0; // exit operation, not needed for tail recursion
    })
    .filter(({ coordinate, n }) => n === environment.numberOfFields)
    .reduce(0, (memo, value) => memo + 1, (x, y) => x + y)
    .then(numberOfOpenTours => console.log(numberOfOpenTours);

The recursion function can therefore be used to generate a sequence of elements - as shown in the knight tour example above.

But the solution above lacks support for automatic work load balancing across the available workers. In fact, the above example only runs on a single worker. Automatic work sharing can be implemented by using a work stealing thread pool - what itself arises new issues.

1. How and when should a new task be scheduled for a recursive function (expand).
2. How to make the worker switch seamless and - more important - transparent. The problem here is, that - up to now - all functors are allowed to access and change any data stored in environment. If work is stolen from one worker and passed on to another, then the model breaks as changes in one worker are not immediately visible to the other. Besides the visibility issue, the environment of the new worker cannot be initialized to exactly the same state as it is / was on the robbed worker, as preceding operations might have changed the state of the environment. Serializing the environment is not an option as functions/objects cannot be serialized.

The second issue might be solved by forbidding access to the environment and instead require explicit passing of the needed - and serializable - variables.