Hosted with the Supercomputer Software Department RAS Home
Parallel Computing Technologies Third International Conference (PaCT-95) September 12-15, 1995. St.-Petersburg, Russia Proceedings Home PaCTs Prev Contents Next Authors
	Vol. 964

Optimal Loop Scheduling on Multiprocessors: A Pumping Lemma for p-Processor Schedules

by F. Gasperoni, U. Schwiegelshohn, J. Turek

Abstract:
This paper addresses the problem of optimally scheduling a cyclic set of interdependent operations (or tasks), representing for instance a program loop. While the existence of optimum periodic schedules has been demonstrated when processors are plentiful, the corresponding problem when the number of available processors is fixed, remains unanswered. In this work we show that if the operations' dependence graph is strongly connected, then there exists a p-processor optimum schedule, for any p, which is expressible in the form of a loop. To prove this result we have established a general pumping lemma for p-processor schedules akin to the classical pumping lemma for regular languages.

Keywords: Theory



Classification:
	C.1	processor architectures
	C.2	computer-communication networks
	C.3	special-purpose and application-based systems; microprocessor/microcomputer applications; process control systems; real-time systems; signal processing systems
	C.4	performance of systems; design studies; measurement techniques; modeling techniques; performance attributes; reliability, availability, and serviceability
	D.1	programming techniques
	D.2	software engineering
	D.3	programming languages
	D.4	operating systems
	F.1	computation by abstract devices
	F.2	analysis of algorithms and problem complexity


Source:
F. Gasperoni, U. Schwiegelshohn, J. Turek, Optimal Loop Scheduling on Multiprocessors: A Pumping Lemma for p-Processor Schedules.
In V. Malyshkin (ed.), Parallel Computing Technologies: Proceedings of the 3th International Conference, Lect. Notes in Comp. Sci., Vol. 964, Springer, 1995, pp. 51-56

ISSN 0302-9743
ISBN 3-540-60222-4

Search LNCS articles for:
Gasperoni, F. ; Schwiegelshohn, U. ; Turek, J.



Scanned first page:

Designed by the Supercomputer Software Department RAS, 1998