Task decomposition for a bus multiprocessor: properties of optimal schedules

A bus oriented multiprocessor contains one bus system to which all the processors are connected. There are one master and several slaves. The most serious problem is the bus bottleneck. At a time, only one slave can establish communications through the bus with the master. A second problem is to keep each processor busy. We suppose we have to execute a task which uses a big amount of data and which can be split into several independent processes. Moreover, the processing time of each process is a linear function of its amount of data. The objective is to minimize the makespan by taking into account communication durations and processing times. At first, the properties of optimal schedules are studied. Next, two particular cases with task computation times proportional to their amounts of data are considered. In the first case, we have one slave and several processes sent to it. So, the processor can compute in masked time after the reception of the first amount of data. In the second case, we have two slaves and only one process is sent to both of them. Finally, we remark that this approach can be generalized.