-
Notifications
You must be signed in to change notification settings - Fork 3
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 the underlining technologies or paradigms. The project does not aim to solve all problems nor to provide a high performance parallelization framework (performance is an important matter, but not the main goal). If performance is the most critical criteria, a plain web worker / child process / you name it implementation should be considered instead.
The library provides at one hand a low level, task based API, and at the other hand a high level reactive API. These APIs are not exclusive, the idea is to provide the appropriate tools to solve a wide set of problems conveniently. The low level API allows to schedule arrow function (lambda) or traditional functions as task on a background worker. The reactive API is based on the low level API and therefore the same memory model applies for both APIs. First, the common memory model is explained, followed by the low level API and finally the reactive programing model is explained.
The ECMAScript defined memory model applies for all functions. However, further restrictions apply for functions executed in a background worker. The library is environment (Browser, NodeJS) independent, therefore the memory model of the library only allows what the least common denominator of all these environments guarantees to be safe. The following section defines the memory model for functions executed on a background worker.
It's very common for JavaScript to access variables from the enclosing Closures. As the function might need to be serialized for transmission to the background worker, access to variables from the enclosing closure are prohibited.
This restriction is weakened if using the static code rewriter. The static code rewriter makes const variables from the enclosing closure available by creating a snapshot. Access to let or var variables however is only allowed if it is (almost) certain that there are no write accesses.
It's to be noted that changes to object structures are not propagated between the main thread and the workers even if access to those objects (as they are defined as const variable) is allowed. As mentioned, the library creates a snapshot of the accessed variables from the enclosing Closure at the moment the task is scheduled onto the thread pool.
Access to this is prohibited for all passed functors as described in the API (is an extended form of accessing variables from the outer closure). The reason therefore is, that the this object is not available on the background worker.
Access to imports is not allowed without using the static code rewriter. The static code rewriter makes imports available to functors, with the restriction, that each worker uses its own instances of the imports. E.g. if one file exports a singleton variable, then the main thread and each worker thread use their own instance of the singleton.
Data passed from the main thread to a background thread - or vice versa - needs to be serializable using the structured clone algorithm. The main consequence of this restriction is, that only data values can be passed but not functions or Errors. Therefore, serialized objects no longer posses any methods.
Structured cloning is a WebAPI and therefore not available in all environments (e.g. NodeJS or older browsers). There exist various libraries implementing the algorithm and therefore can be applied if needed. However, for most circumstances the JSON serialization should be sufficient anyway (main advantage is to support cyclic structures).
The low level API is mostly described by the parallel.schedule(function): ITask method and allows to execute a single function on a worker thread. The task implements the Promise API for error handling and querying the result. The API is offered for users needing full control over the task and how the problem is parallelized.
parallel.schedule(function (arg) {
// compute
return value;
}, 10).then(result => console.log(result), reason => console.error(reason));The current implementation does not provide any further low level constructs like joining, locks or semaphores. As JavaScript does not have shared memory, further investigation is needed for each of these features to clarify if they are reasonable in this environment or if better alternatives exist. However, these construct might be useful to solve more sophisticated problems.
parallel
.range(100000)
.filter(value => value % 2 === 0)
.map(value => value ** 2)
.subscribe((subResult, taskIndex) => console.log(`Sub Result from ${taskIndex}`, subResult))
.then(result => console.log("End result", result);The reactive API provides an even more convenient method for solving problems in parallel and therefore taking benefit of the computation power available on modern devices. The reactive API is data flow based. The user describes how the data is to be transformed and the implementation takes care of splitting the work into tasks and coordinating them. The aim of the API is to provide a very convenient way to perform computations parallel without the need to understand the underlining details but still offering enough control for fine tuning.
The main benefits of a reactive API is that the API describes the intent of the user. This information about the intent can be used by the runtime to split the work into multiple tasks and find an appropriate scheduling without any further steps required by the user - making the API simpler to use. However, the API allows the user to fine tune the scheduling 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.
Further restrictions apply for the reactive API.
There is the possibility to define an environment for a parallel job.
parallel.from([1, 2, 3, 4])
.inEnvironment({ exponent: 10 })
.map((value, environment) => value ** environment.exponent)
.then(result => console.log(result));The environment is an object structure that allows to pass additional data from the main thread to the background worker or storing state for a specific worker instance. The environment state is worker local and therefore, changes are not reflected between the web workers executing the parallel job nor is the environment available after completion of the task.
This section describes further, possible extensions to support more sophisticated operations. The section describes the motivation, problems facing and possible solutions.
The current implementation performs a single task on a worker and if the task is complete, the result is transferred back to the main thread. As message passing is one of the main bottlenecks, task continuation should be supported. Task continuation allows to define a second task that builds up onto the result computed by the previous task. If the first task completes, the worker directly continues with the second task (that continues the first one).
If this approach is combined with a work stealing thread pool, the reactive job scheduling might be dramatically optimized. Each Operation could then be represented as a single task, continued by the following operation. If the operations are not balanced equally across the worker threads (e.g. if a problem is not linear and some worker complete earlier then others), then the work could be rebalanced. The problem faced is, that the environment is defined for the whole chain and a worker stealing work from another worker needs to have the exact same environment as from the worker the work has been stolen from. This limits the use cases how the environment might be used.
-> Only allow the environment for a single operation instead of for a whole parallel chain. This allows to reassign the tasks to worker as long as the operation has not been scheduled?
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 of the returned array.
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.
- How and when should a new task be scheduled for a recursive function (
expand). - 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.