| 1. |
- Laksman, Efraim, et al.
(författare)
-
Generalized upper bounds on the minimum distance of PSK block codes
- 2015
-
Ingår i: IMA Journal of Mathematical Control and Information. - : Oxford Journals. - 0265-0754 .- 1471-6887. ; 32:2, s. 305-327
-
Forskningsöversikt (refereegranskat)abstract
- This paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase shift keying (PSK) block codes, that are explicit in three parameters: alphabet size, block length and code size. The bounds are primarily generalized from codes over symmetric PSK to codes over asymmetric PSK and also to general alphabet size. Furthermore, block codes are optimized in the presence of other types of noise than Gaussian, which induces also non-Euclidean distance measures. In some instances, codes over asymmetric PSK prove to give higher Euclidean distance than any code over symmetric PSK with the same parameters. We also provide certain classes of codes that are optimal among codes over symmetric PSK.
|
|
| 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. |
- Lundberg, Lars, et al.
(författare)
-
Using Golomb Rulers for Minimizing Collisions in Closed Hashing
- 2004
-
Konferensbidrag (refereegranskat)abstract
- We give conditions for hash table probing which minimize the expected number of collisions. A probing algorithm is determined by a sequence of numbers denoting jumps for an item during multiple collisions. In linear probing, this sequence consists of only ones – for each collision we jump to the next location. To minimize the collisions, it turns out that one should use the Golomb ruler conditions: consecutive partial sums of the jump sequence should be distinct. The commonly used quadratic probing scheme fulfils the Golomb condition for some cases. We define a new probing scheme – Golomb probing - that fulfills the Golomb conditions for a much larger set of cases. Simulations show that Golomb probing is always better than quadratic and linear and in some cases the collisions can be reduced with 25% compared to quadratic and with more than 50% compared to linear.
|
|
| 5. |
- Klonowska, Kamilla, et al.
(författare)
-
Comparing the optimal performance of parallel architectures
- 2004
-
Ingår i: Computer journal. - Oxford : Oxford University Press. - 0010-4620 .- 1460-2067. ; 47:5, s. 527-544
-
Tidskriftsartikel (refereegranskat)abstract
- Consider a parallel program with n processes and a synchronization granularity z. Consider also two parallel architectures: an SMP with q processors and run-time reallocation of processes to processors, and a distributed system (or cluster) 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 H(n,k,q,t,z) such that the minimum completion time for all programs with n processes and a granularity z is at most H(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 H(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 H(n,k,q,t,z). We also validate our results using measurements on distributed and multiprocessor Sun/Solaris environments. The function H(n,k,q,t,z) provides important insights regarding the performance implications of the fundamental design decision of whether to allow run-time reallocation of processes or not. These insights can be used when doing the proper cost/benefit trade-offs when designing parallel execution platforms.
|
|
| 6. |
- Klonowska, Kamilla, et al.
(författare)
-
Extended Golomb Rulers as the New Recovery Schemes in Distributed Dependable Computing
- 2005
-
Konferensbidrag (refereegranskat)abstract
- Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down the load on these computers must be redistributed to other computers in the cluster. The redistribution is determined by the recovery scheme. The recovery scheme should keep the load as evenly distributed as possible even when the most unfavorable combinations of computers break down, i.e. we want to optimize the worst-case behavior. We have previously defined recovery schemes that are optimal for some limited cases. In this paper we find a new recovery schemes that are based on so called Golomb rulers. They are optimal for a much larger number of cases than the previous results.
|
|
| 7. |
- Klonowska, Kamilla, et al.
(författare)
-
Optimal recovery schemes in fault tolerant distributed computing
- 2005
-
Ingår i: Acta Informatica. - : Springer. - 0001-5903 .- 1432-0525. ; 41:6, s. 341-365
-
Tidskriftsartikel (refereegranskat)abstract
- Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all n computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down, the load on these computers must be redistributed to other computers in the system. The redistribution is determined by the recovery scheme. The recovery scheme is governed by a sequence of integers modulo n. Each sequence guarantees minimal load on the computer that has maximal load even when the most unfavorable combinations of computers go down. We calculate the best possible such recovery schemes for any number of crashed computers by an exhaustive search, where brute force testing is avoided by a mathematical reformulation of the problem and a branch-and-bound algorithm. The search nevertheless has a high complexity. Optimal sequences, and thus a corresponding optimal bound, are presented for a maximum of twenty one computers in the distributed system or cluster.
|
|
| 8. |
- 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.
|
|
| 9. |
- Lennerstad, Håkan, et al.
(författare)
-
Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling
- 2007
-
Ingår i: Real-time systems. - Dordrecht : Kluwer Academic Publishers. - 0922-6443 .- 1573-1383. ; 35:2, s. 135-151
-
Tidskriftsartikel (refereegranskat)abstract
- We provide a constant time schedulability test for an on-line multiprocessor server handling aperiodic tasks. Dhall's effect is avoided by dividing the tasks in two priority classes based on task utilization: heavy and light. We prove that if the load on the multiprocessor server stays below U threshold = 3 - root 7 approximately equals 35.425%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. The same number 35.425% is also a threshold for a task to be characterized as heavy. The bound U threshold = 3 - root 7 approximately equals 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor system. Assuming the server to be equipped with m processors, we calculate a formula for the sharp bound U threshold (m), which converges to U threshold from above as m -> infinity . The results are based on a utilization function u(x) = 2(1 - x)/(2 + root 2+2x). By using this function, the performance of the multiprocessor server can in some cases be improved beyond U threshold(m) by paying the extra overhead of monitoring the individual utilization of the current tasks.
|
|
| 10. |
- Lennerstad, Håkan
(författare)
-
Local Linear Time Convergence of a Primal-Dual Energy Minimization Algorithm for Parallel Processing
- 2014
-
Konferensbidrag (refereegranskat)abstract
- We consider energy minimization by speed-scaling of an open shop multiprocessor with n jobs and m machines. The paper studies the complexity of a primal-dual solution algorithm of [4], which was an open question in that paper.We prove that in a neighbourhood of the solution the complexity of the algorithm is O(mn log(1/ε) if n and m are not equal and ε is the roundoff error of the computer. The paper demonstrates how linearization can be used to investigate the complexity of an algorithm close to the optimum. An estimate of the size of the neighbourhood where the linearization error is smaller than the computer’s roundoff error is also given.
|
|
