A self-modifiable approach to scheduling and mapping algorithms in multiprocessor systems

Abstract

A formal method for scheduling algorithms in multiprocessor architectures is presented. The approach can be used for synthesis of processes in distributed systems and massively parallel architectures with asynchronous or synchronous parallelism. It is assumed that a global virtual job to be performed is given, and is necessary to subdivide it into subtasks performed by individual processors and to add appropriate communication and synchronization structure to preserve a final global job intact This task is performed using a formal environment of the Calculus of Self-Modifiable Algorithms-a generic tool for parallel problem solving. Due to the generality of the approach, it can be used in a majority of parallel environments.

Keywords:

• Scheduling
• multiprocessor system
• parallelism
• self-modification

C.R. Categories:

• C.1.2
• F.1.1
• F.1.2
• F.2.2

^‡The research of both authors are partially supported by research grants from the Natural Sciences and Engineering Research Council of Canada, OGP0046501 and OGP0036838 respectively.

^‡The research of both authors are partially supported by research grants from the Natural Sciences and Engineering Research Council of Canada, OGP0046501 and OGP0036838 respectively.

Notes

^‡The research of both authors are partially supported by research grants from the Natural Sciences and Engineering Research Council of Canada, OGP0046501 and OGP0036838 respectively.