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 |
