Ideas about parallel modules

[samiam95124]

Further extensions for parallel modules

The existing Pascaline specification has the module types:

process
monitor
share

Processes start a new thread and give the ability to declare globals, public or private, in the process module. A process module cannot call regular modules or program modules. It can call share modules or monitors. Recall a process is a thread of execution plus a collection of global data. In this scheme of things, a program is the main (default) process.

A monitor is a module that can communicate between processes, or between the process modules and the program module. It (basically) only takes value (or view) parameters and cannot pass pointers. It can only itself call other monitors or share modules, which can effectively restrict it to value (or view) parameters without pointers, but only when calling other monitors. monitors can call share modules in any mode, including var and pointers.

A share module can be called or used by any other module in the system, including process modules, program modules, monitors, shares, etc. It can do that because it has no globals at all.

This parallel module system is actually already in place and working in IP Pascal, so it is well tested.

New module types

I propose the following new module types. Comments are welcome. The name(s) are not set in cement.

Group modules

The first is group modules. The issue with process modules is that you can only declare globals in that process module that owns the thread. A group module is declared:

module of procname alpha(input, output, data);

...

A group module appears as a normal module, but it is keyed to the process by name. It can have globals, public or private, but can only use declarations from other modules or process that has the same name. Thus:

process myprocess;

module of myprocess a;

module of myprocess b;

Are all in the group myprocess and can access all the declarations in the group. It is strictly by name, that is, when compiling a module, the compiler only needs to match the name of the process it belongs to.

The program main process fits into this by default:

program myprogram;

module of myprogram a;

module of myprogram b;

Is the same as saying:

program myprogram;

module a;

module b;

Friend modules

A friend module appears as:

friend a;

It appears just as a normal module. It can have globals, public or private, and it can be used by any other module, program, module, process, monitor, share, etc. The trick is that a friend module keeps its global data on a per-process or per thread basis. Thus:

friend a;

var i: integer

.

module b;

joins a;

begin

    a.i := 42

end.

module of myprocess c;

joins a;

begin

    writeln('The value of a.i is: ', a.i)

end

.

Would result in two different versions of a.i, one for the main process (program) and another for the subprocess c. Thus they are unable to share data. Thus the main process sets a.i is 42, but the subprocess myprocess does not see that. It sees 0 or an uninitialized variable.

The trick that makes friend modules work is that each access to globals in the friend are done via a base pointer in a task table in the friend module. The accessor module finds the base pointer by adding its thread logical id to the task table base, then uses that base offset to access globals in the friend.

When a friend module initalizes, it calls a function that inserts it into a table so that it gets a callback when the thread task is created (any thread). This gives the friend module a chance to allocate a block of data equal to the size of globals in the module. Then it plants that base address in its task table. When a thread is terminated, the friend module is called again to remove the global access block.

Costs

Group modules are free. That is, it just takes a compiler check to see if the modules are using the same name. When compiling module x for group y, each used or joined module is verified to have the same group name.

friend modules have no cost for calls, type definitions, etc. For globals, each access is the cost of a base offset pointer that must be picked up from the friend table. Its about equivalent in cost to accessing locals on a different procedure/function level. Not the same level of locals, because those are accessed via the frame pointer, but a higher level frame where the base pointer must be obtained. Thus the cost is not zero, but not that bad, either.

Its important to note that after the base offset, friend accesses don't carry cost. A var or other pointer to a friend global can be kept essentially forever, because access to it is only terminated with the termination of the accessing thread.

Objects!

If you follow along with the Pascaline manual, you will know that Pascaline implements objects as "modules, light", and thus for every module type there is a class type. Thus I need to have a think what the class analog is for these new modules.

Credits

The idea that parallel tasking could be largely secured by a compiler is due to the late Per Brinch Hansen.

[samiam95124]

The problem with friend modules

The issue with friend modules is that a module outside of a process module does not know in advance what thread it is on. Its called by another module, does not have a particular module it is assigned to, and thus must perform any calculation at the time of globals accesses. For a module that knows its thread, like a process, it can precalculate the global address base of a used/joined module and store the address at startup time. Other modules can find the thread id, but have to perform any calculation again. This is a major barrier to efficiency.

Group modules do not have this issue.