| 41561. |
- Lennerstad, Håkan, et al.
(författare)
-
An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems
- 1992
-
Rapport (övrigt vetenskapligt/konstnärligt)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 maximal execution time ratio $g(n,k)=\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 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.
|
|
| 41562. |
- Lennerstad, Håkan
(författare)
-
Commensurable and rational triangles
- 2007
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- One may ask which property the equilateral, the right isosceles, the half equilateral, and the two golden triangles, with angles (π/5),((2π)/5),((2π)/5) and (π/5),(π/5),((3π)/5), have in common. One answer is that their angles are commensurable with each other -- such triangles are commensurable. We investigate properties of this class of triangles, which is a countable subset of the entire class of triangles -- we do not distinguish between similar triangles. It can naturally be endowed with a family structure by integer triples. The equilateral is the only member of the first generation, and the other triangles mentioned above populate the first generations. A formula for the number of non-similar triangles that can be formed by triples of corners in a regular n-polygon is calculated, which gives the number of commensurable triangles at each generation. Three "metatriangles" are described -- so called because each possible triangle is represented as a point in each of them. The set of right triangles form a height in one of the metatriangles. The eye is the point of a metatriangle in the same metatriangle. In the second part of this report, triangles are studied by side length. A rational triangle is a triangle where all sides and all heights are rational numbers. We show that the right rational triangles are the Pythagorean triangles, and each non-right rational triangle consists of two Pythagorean triangles. Almost all triangles are irrational. It turns out that no Pythagorean triangle is commensurable. We prove that the only triangle with commensurable angles and also commensurable sides is the equilateral triangle.
|
|
| 41563. |
- Lennerstad, Håkan, et al.
(författare)
-
Generalizations of the floor and ceiling functions using the Stern-Brocot tree
- 2006
-
Rapport (refereegranskat)abstract
- We consider a fundamental number theoretic problem where practial applications abound. We decompose any rational number a/b in c ratios as evenly as possible while maintaining the sum of numerators and the sum of denominators. The minimum and maximum of the ratios give rational estimates of a/b from below and from above. The case c=b gives the usual floor and ceiling functions. We furthermore define the max-min-difference, which is zero iff c≤GCD(a,b), quantifying the distance to relative primality. A main tool for investigating the properties of these quantities is the Stern-Brocot tree, where all positive rational numbers occur in lowest terms and in size order. We prove basic properties such that there is a unique decomposition that gives both the minimum and the maximum. It turns out that this decomposition contains at most three distinct ratios. The problem has arisen in a generalization of the 4/3-conjecture in computer science.
|
|
| 41564. |
- Lennerstad, Håkan, et al.
(författare)
-
Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems
- 1993
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- For the execution of an arbitrary parallel program P, consisting of a set of processes, we consider two alternative multiprocessors. The first multiprocessor has q processors and allocates parallel programs dynamically, i.e. processes may be reallocated from one processor to another. The second employs cluster allocation with k clusters and u processors in each cluster - here processes may be reallocated within a cluster only. Let T_d(P,q) and T_c (P,k,u) be execution times for the parallel program P with optimal allocations. We derive a formula for the program independent performance function G(k,u,q)=\sup_ all parallel programs P T_c(P,k,u)}{T_d(P,q)}. Hence, with optimal allocations, the execution of $P$ can never take more than a factor $G(k,u,q)$ longer time with the second multiprocessor than with the first, and there exist programs showing that the bound is sharp. The supremum is taken over all parallel programs consisting of any number of processes. Any interprocess dependency structure is allowed for the parallel programs, except deadlock. Overhead for synchronization and reallocation is neglected only. We further present optimal formulas which exploits a priori knowledge of the class of parallel programs intended for the multiprocessor, thus resulting in sharper optimal bounds. The function g(n,k,u,q) is the above maximum taken over all parallel programs consisting of n processes. The function s(n,v,k,u) is the same maximum, with q=n, taken over all parallel programs of $n$ processes which has a degree of parallelism characterized by a certain parallel profile vector v=(v_1,...,v_n). The functions can be used in various ways to obtain optimal performance bounds, aiding in multiprocessor architecture decisions. An immediate application is the evaluation of heuristic allocation algorithms. It is well known that the problems of finding the corresponding optimal allocations are NP-complete. We thus in effect present a methodology to obtain optimal control of NP-complete scheduling problems.
|
|
| 41565. |
- 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.
|
|
| 41566. |
- 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.
|
|
| 41567. |
- Lennerstad, Håkan
(författare)
-
The n-dimensional Stern-Brocot tree
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The n-dimensional Stern-Brocot tree consists of all sequences (p₁, ...,p_{n}) of positive integers with no common multiple. The relatively prime sequences can be generated branchwise from each other by simple vector summation, starting with an ON-base, and controlled by a generalized Euclidean algorithm.The tree induces a multiresolution partition of the first quadrant of the (n-1)-dimensional unit sphere, providing a direction approximation property of a sequence by its ancestors. Two matrix representations are introduced, where in both a matrix contains the parents of a sequence. From one of them the isomorphism of a subtree to the entire tree of dimension equal to the number of parents of the top sequence follows. A form of Fibonacci sequences turn out to be the sequences of fastest growing sums. The construction can be regarded an n-dimensional continued fraction, and it may invite further n-dimesional number theory.
|
|
| 41568. |
|
|
| 41569. |
|
|
| 41570. |
|
|
