Processor utilization in a linearly connected parallel processing system

The authors study the problem of assigning program fragments to a system of processing elements in which low-level operations are performed in parallel. Such a system is said to be linearly connected if each processing element can only communicate directly with its two nearest neighbors. They show that the problem of determining whether a perfect assignment exists is NP-complete but can be solved in linear time if the number of processing elements is fixed. They demonstrate that the related problem of determining whether any assignment exists which can be performed in a given number of machine cycles is NP-complete. For this problem, the objective of which corresponds to minimizing the program fragment´s execution time, the authors also investigate the behavior of classes of near-optimal heuristic algorithms. This present evidence to indicate that guaranteeing acceptable worst-case performance is a very difficult problem as well