As a result of the scheduling phase, the computational subprocesses decomposed from the same original coarse-grain process are mapped to the same type of processor implementation or custom ICs. They have not however been mapped to the same instance of the processor or custom IC.
Our first step is to regroup these subprocesses back into their coarse-grain process and assign them to the same processor instance. From then on, the allocation and binding procedure will treat the regrouped subprocesses as a single process.
Processes are generally separated into different classes if they are mapped to different types of hardware units. Within each class, the allocation and binding (sharing) is then performed.
Processes which are mapped to programmable units can share the same instance of the unit through TDM even if their lifetimes overlap. In addition to the programmable communication units, part of the buses or the shared memory and/or local buffers needed for communication may be shared in a TDM fashion by the the corresponding communication processes. The requirements for sharing one programmable unit instance are that the processes are mapped to the same type of unit, and the sum of the utilization factors of those processes is less than 100 percent. We perform the allocation and binding by using a modified bin packing algorithm which ensures that every regrouped coarse-grain process is bound to the same hardware instance throughout its lifetime. Note that the TDM sharing does not change the global timing obtained in the scheduling phase. Details are omitted to save space.
For non-programmable units such as custom ICs or other communication units, sharing is possible only if the process lifetimes do not overlap or the processes are mutually exclusive.