Search

In parallel processing in a multiprocessor system, it is necessary to partition the user program and data to be distributed to the processors, that is, to apply scheduling. It is difficult to realize the scheduling under arbitrary conditions without any restriction of precedence constraints, number of employed processors, the multiprocessor configuration, and the communication time, by an algorithm with optimized polynomial time. Thus, the application of a heuristic algorithm is considered. This paper is based on the critical path (CP) method, and proposes a scheduling method which can be used in multiprocessor systems with various topologies, including perfect and imperfect connections. The proposed method resembles the existing method in that the task is assigned, but has the feature that the assignment is corrected and optimized from the viewpoint of the communication time. The allocation of processors and adequate modification of hopping are also considered. The effectiveness of the proposed method is evaluated through comparison to existing methods using the same task graph. In order to evaluate its effectiveness when applied to a large-scale system, the method was implemented on a real system (a system with 32 DSP), and an analysis program for an electrical power system was run. The proposed method was demonstrated to be uniformly useful for various topologies, and exhibits sufficient performance in practice. © 2003 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 87(1): 63–75, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.10212 [ABSTRACT FROM AUTHOR]

Scheduling is a typical technique used to distribute the load in multiprocessor systems. Usually, the manager(dispatcher or operating system)schedule the tasks so that the average finish time is minimized. Constraints related to the characteristics of the load such as precedence relation, deadline time, etc. must be taken into consideration. With ever increasing applications of a new paradigm of divisible tasks in image processing and parallel processing, one must concentrate on the characteristics of the system such as processor speed, link speed, and processor interconnection topology when distributing the load. By exploiting queuing theory, we managed to find different bounds on the arrival rate(load) as a function of link speed, processor speed and the size of tasks. A flow control mechanism for different multiprocessor systems with different topologies is embedded in our analysis. Moreover, our model indicates to the design engineers, depending on the traffic intensity, which element(s)of a parallel system has to be upgraded or replaced to meet the new load. This, of course, has to be justified by cost consideration. [ABSTRACT FROM AUTHOR]