Combinatorics for multiprocessor scheduling optimization and other contexts in computer architecture

Document type: Conference Papers
Peer reviewed: Yes
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Combinatorics for multiprocessor scheduling optimization and other contexts in computer architecture
Conference name: Combinatorics and Computer Science. 8th Franco-Japanese and 4th Franco-Chinese Conference
Year: 1996
Pagination: ix+415
ISBN: 3540615768
Publisher: Springer-Verlag; Berlin, Germany
City: Brest, France
Organization: Blekinge Institute of Technology
Department: Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)
Dept. of Telecommunications and Mathematics S-371 79 Karlskrona
+46 455 780 00
http://www.hk-r.se/itm/index.html
Authors e-mail: hakan.lennerstad@itm.hk-r.se
Language: English
Abstract: The method described consists of two steps. First, unnecessary programs are eliminated through a sequence of program transformations. Second, within the remaining set of programs, sometimes regarded as matrices, those where all possible combinations of synchronizations occur equally frequently are proven to be extremal. At this stage we obtain a formulation which is simple enough to allow explicit formulas to be derived. It turns out that the same method can be used for obtaining worst-case bounds on other NP-hard problems within computer architecture.
Subject: Computer Science\Computersystems
Computer Science\Distributed Computing
Mathematics\Discrete Mathematics
Keywords: Combinatorial mathematics, computational complexity, optimisation, processor scheduling, synchronisation
Edit