| 1. |
- Lennerstad, Håkan, et al.
(författare)
-
An Optimal Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems
- 1995
-
Ingår i: SIAM journal on computing (Print). - Philadelphia, Pa. : SIAM publications. - 0097-5397 .- 1095-7111. ; 24:4, s. 751-764
-
Tidskriftsartikel (refereegranskat)abstract
- Consider a multiprocessor with k identical processors, executing parallel programs consisting of n processes. Let T$-s$/(P) and T$-d$/(P) denote the execution times for the program P with optimal static and dynamic allocations, respectively, i.e., allocations giving minimal execution time. We derive a general and explicit formula for the following maximal execution time ratio: g(n, k) $EQ max T$-s$/(P)/T$-d$/(P), where the maximum is taken over all programs P consisting of n processes. Any interprocess dependency structure for the programs P is allowed only by avoiding deadlock. Overhead for synchronization and reallocation is neglected. Basic properties of the function g(n, k) are established, from which we obtain a global description of the function. Plots of g(n, k) are included. The results are obtained by investigating a mathematical formulation. The mathematical tools involved are essentially tools of elementary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to extremal programs. It is mathematically complicated but rapidly computed for reasonable n and k, in contrast to the np-completeness of the problems of finding optimal allocations.
|
|
| 2. |
- Lennerstad, Håkan, et al.
(författare)
-
Combinatorics for multiprocessor scheduling optimization and other contexts in computer architecture
- 1996
-
Konferensbidrag (refereegranskat)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.
|
|
| 3. |
- Lennerstad, Håkan
(författare)
-
Logical graphs : how to map mathematics
- 1996
-
Ingår i: ZDM - Zentralblatt für Didaktik der Mathematik. - : Taylor & Francis. - 0044-4103. ; 27:3, s. 87-92
-
Tidskriftsartikel (refereegranskat)abstract
- A logical graph is a certain directed graph with which any mathematical theory or proof can be presented - its logic is formulated in graph form. Compared to the usual narrative description, the presentation usually gains in survey, clarity and precision. A logical graph formulation can be thought of as a detailed and complete map over the mathematical landscape. The main goal in the design of logical graphs is didactical: to improve the orientation in a mathematical proof or theory for a reader, and thus to improve the access of mathematics.
|
|
| 4. |
- Lennerstad, Håkan, et al.
(författare)
-
Optimal Scheduling Results for Parallel Computing
- 1996
-
Ingår i: Applications on advanced architecture computers. - Philadelphia, USA : SIAM. - 0898713684 ; , s. 155-164
-
Bokkapitel (refereegranskat)abstract
- Load balancing is one of many possible causes of poor performance on parallel machines. If good load balancing of the decomposed algorithm or data is not achieved, much of the potential gain of the parallel algorithm is lost to idle processors. Each of the two extremes of load balancing - static allocation and dynamic allocation - has advantages and disadvantages. This chapter illustrates the relationship between static and dynamic allocation of tasks.
|
|
| 5. |
- Lennerstad, Håkan, et al.
(författare)
-
Optimal Worst Case Formulas Comparing Cache Memory Associativity
- 1995
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Consider an arbitrary program $P$ which is to be executed on a computer with two alternative cache memories. The first cache is set associative or direct mapped. It has $k$ sets and $u$ blocks in each set, this is called a (k,u)$-cache. The other is a fully associative cache with $q$ blocks - a $(1,q)$-cache. We present formulas optimally comparing the performance of a $(k,u)$-cache compared to a $(1,q)$-cache for worst case programs. Optimal mappings of the program variables to the cache blocks are assumed. Let $h(P,k,u)$ denote the number of cache hits for the program $P$, when using a $(k,u)$-cache and an optimal mapping of the program variables of $P$ to the cache blocks. We establish an explicit formula for the quantity $$\inf_P \frac{h(P,k,u)}{h(P,1,q)},$$ where the infimum is taken over all programs $P$ which contain $n$ variables. The formula is a function of the parameters $n,k,u$ and $q$ only. We also deduce a formula for the infimum taken over all programs of any number of variables, this formula is a function of $k,u$ and $q$. We further prove that programs which are extremal for this minimum may have any hit ratio, i.e. any ratio $h(P,1,q)/m(P)$. Here $m(P)$ is the total number of memory references for the program P. We assume the commonly used LRU replacemant policy, that each variable can be stored in one memory block, and is free to be stored in any block. Since the problems of finding optimal mappings are NP-hard, the results provide optimal bounds for NP-hard quantities. The results on cache hits can easily be transformed to results on access times for different cache architectures.
|
|
| 6. |
- Lennerstad, Håkan
(författare)
-
The directional display
- 1997
-
Konferensbidrag (refereegranskat)abstract
- The directional display contains and shows several images-which particular image is visible depends on the viewing direction. This is achieved by packing information at high density on a surface, by a certain back illumination technique, and by explicit mathematical formulas which eliminate projection deformations and make it possible to automate the production of directional displays. The display is illuminated but involves no electronic components. Patent is pending for the directional display. Directional dependency of an image can be used in several ways. One is to achieve three-dimensional effects. In contrast to that of holograms, large size and full color involve no problems. Another application of the technique is to show moving sequences. Yet another is to make a display more directionally independent than conventional displays. It is also possible and useful in several contexts to show different text in different directions with the same display. The features can be combined.
|
|
| 7. |
- Lennerstad, Håkan
(författare)
-
The Geometry of the Directional Display
- 1996
-
Rapport (refereegranskat)abstract
- The directional display is a new kind of display which can contain and show several images -which particular image is visible depends on the viewing direction. This is achieved by packing information at high density on a surface, by a certain back illumination technique, and by explicit mathematical formulas which make it possible to automatize the printing of a display to obtain desired effects. The directional dependency of the display can be used in several different ways. One is to achieve three-dimensional effects. In contrast to that of holograms, large size and full color here involve no problems. Another application of the basic technique is to show moving sequences. Yet another is to make a display more directionally independent than today’s displays. Patent is pending for the invention in Sweden.
|
|
| 8. |
- Lundberg, Lars, et al.
(författare)
-
An Optimal Lower Bound on the Maximal Speedup in Multiprocessors with Clusters
- 1995
-
Konferensbidrag (refereegranskat)abstract
- We consider an ideal multiprocessor system with q processors and a centralized scheduler without overhead that select processes from one common pool, permitting dynamic relocation of processes. A parallel program P consisting of n processes is executed on this system and terminates when all processes are completed. Due to synchronizations, processes may be blocked while waiting for events in other processes. The parallel program is executed using some schedule of processes to processors, resulting in a speedup $sigma@. We then consider an ideal multiprocessor with k clusters containing u processors each. In this system processes may not be relocated between clusters. Finding a schedule which results in maximum speedup is NP-hard. Here, we present a formula for the optimal lower bound on the maximum speedup for program P, as a function of q, n, $sigma@, k and u. We also present a formula for the optimal lower bound when the number of processes (n) is unknown. Using these results we are able to decide if a certain schedule is close to optimal or if it is worth-while to look for other schedules. This is demonstrated by evaluating the speedup of a specific schedule of a particular program.
|
|
| 9. |
- Lundberg, Lars, et al.
(författare)
-
Bounding the gain of changing the number of memory modules in shared memory multiprocessors
- 1997
-
Ingår i: Nordic Journal of Computing. - Finland : Publishing Assoc. Nordic Journal of Comput. - 1236-6064. ; 4:3, s. 233-58
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a multiprocessor, with p processors and m memory modules. If more than one processor want to access a memory module simultaneously, these accesses will be serialized due to memory contention. The completion time of a program executing on this system is thus affected by the way addresses are mapped onto memory modules, and finding a mapping which results in minimal completion time is NP-hard. If we change the number of memory modules from m to m’, while keeping the number processors constant, we will generally change the minimal completion time. The gain of changing the number of memory modules from m to m’ for a certain program is defined as the ratio between the minimal completion times, using m and m’ modules respectively. Here, we present an optimal upper bound on the maximum gain of changing the number of memory modules, as a function of m, m’ and p, including the case when m’ is infinitely large. The bound is obtained by investigating a mathematical formulation. The mathematical tools involved are essentially elementary combinatorics. The formula for calculating the bound is mathematically complicated but can be rapidly computed for reasonable m, m’ and p. This bound makes it possible to do price-performance trade-offs and to compare any mapping of addresses to memory modules with the optimal case. The results are applicable to different multiprocessor architectures, e.g. systems with crossbar networks and systems with multiple buses. The results also make it possible to calculate optimal performance bounds for multiprocessors containing cache memories: as well as for multiprocessors with no cache memories. Moreover, we discuss how the results can be used for calculating bounds for programs with as well as without synchronizations.
|
|
| 10. |
|
|
