Comparing the Optimal Performance of Multiprocessor Architectures
| Document type: | Conference Papers |
|---|---|
| Peer reviewed: | Yes |
| Author(s): | Lars Lundberg, Kamilla Klonowska, Magnus Broberg, Håkan Lennerstad |
| Title: | Comparing the Optimal Performance of Multiprocessor Architectures |
| Conference name: | 21st IASTED International Multi-Conference Applied Informatics |
| Year: | 2003 |
| Pagination: | 750-760 |
| ISBN: | 0889863415 |
| Publisher: | Int. Assoc. of Science and Technology for Development, Calgery - Alberta, T3B OM6, Canada |
| City: | Innsbruck, Austria |
| Organization: | Blekinge Institute of Technology |
| Department: | Department of Software Engineering and Computer Science (Institutionen för programvaruteknik och datavetenskap) Dept. of Software Engineering and Computer Science S-372 25 Ronneby +46 455 38 50 00 http://www.bth.se/eng/ipd/ |
| Authors e-mail: | lars.lundberg@bth.se, kamilla.klonowska@bth.se, magnus.broberg@bth.se, hakan.lennerstad@bth.se |
| Language: | English |
| Abstract: | Consider a parallel program with n processes and a synchronization granularity z. Consider also two multiprocessors: a multiprocessor with q processors and run-time reallocation of processes to processors, and a multiprocessor with k processors and no run-time reallocation. There is an inter processor communication delay of t time units for the system with no run-time reallocation. In this paper we define a function g(n,k,q,t,z) such that the minimum completion time for all programs with n processes and a granularity z is at most g(n,k,q,t,z) times longer using the system with no reallocation and k processors compared to using the system with q processors and run-time reallocation. We assume optimal allocation and scheduling of processes to processors. The function g(n,k,q,t,z) is optimal in the sense that there is at least one program, with n processes and a granularity z, such that the ratio is exactly g(n,k,q,t,z). We also validate our results using measurements on distributed and multiprocessor Sun/Solaris environments. |
| Subject: | Computer Science\Computersystems |
| Keywords: | Multiprocessing systems, Computer architecture, Resource allocation, Scheduling, Synchronization, Computational complexity, Distributed system, Multiprocessors, Optimal bounds |
