Change search
Refine search result
12 1 - 50 of 61
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Adolfsson, Vilhelm
    et al.
    Goldberg, Max
    Jawerth, Björna
    Lennerstad, Håkan
    Localized Galerkin Estimates for Boundary Integral Equations on Lipschitz Domanis1992In: SIAM Journal on Mathematical Analysis, Vol. 5, no 23, p. 751-764Article in journal (Refereed)
    Abstract [en]

    The Galerkin method is studied for solving the boundary integral equations associated with the Laplace operator on nonsmooth domains. Convergence is established with a condition on the meshsize, which involves the local curvature on certain approximating domains. Error estimates are also proved, and the results are generalized to systems of equations.

  • 2.
    Klonowska, Kamilla
    et al.
    Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering.
    Lennerstad, Håkan
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    Lundberg, Lars
    Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering.
    Svahnberg, Charlie
    Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering.
    Optimal recovery schemes in fault tolerant distributed computing2005In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 41, no 6, p. 341-365Article in journal (Refereed)
    Abstract [en]

    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.

  • 3. Klonowska, Kamilla
    et al.
    Lundberg, Lars
    Lennerstad, Håkan
    The maximum gain of increasing the number of preemptions in multiprocessor scheduling2009In: ACTA INFORMATICA, ISSN 0001-5903 , Vol. 46, no 4, p. 285-295Article in journal (Refereed)
    Abstract [en]

    We consider the optimal makespan C(P, m, i) of an arbitrary set P of independent jobs scheduled with i preemptions on a multiprocessor with m identical processors. We compare the ratio for such makespans for i and j preemptions, respectively, where i < j. This ratio depends on P, but we are interested in the P that maximizes this ratio, i. e. we calculate a formula for the worst case ratio G(m, i, j) defined as G(m, i, j) = max C(P, m, i)/C(P, m, j), where the maximum is taken over all sets P of independent jobs.

  • 4. Klonowska, Kamilla
    et al.
    Lundberg, Lars
    Lennerstad, Håkan
    Using Modulo Golomb Rulers for Optimal Recovery Schemes in Distributed Computing2003Conference paper (Refereed)
  • 5. Klonowska, Kamilla
    et al.
    Lundberg, Lars
    Lennerstad, Håkan
    Broberg, Magnus
    Comparing the optimal performance of parallel architectures2004In: Computer journal, ISSN 0010-4620, E-ISSN 1460-2067, Vol. 47, no 5, p. 527-544Article in journal (Refereed)
    Abstract [en]

    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.
    Lundberg, Lars
    Lennerstad, Håkan
    Svahnberg, Charlie
    Extended Golomb Rulers as the New Recovery Schemes in Distributed Dependable Computing2005Conference paper (Refereed)
    Abstract [en]

    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.
    Lundberg, Lars
    Lennerstad, Håkan
    Svahnberg, Charlie
    Using Modulo Rulers for Optimal Recovery Schemes in Distributed Computing2004Conference paper (Refereed)
    Abstract [en]

    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 define recovery schemes, which are optimal for a larger number of computers down than in previous results. We also show that the problem of finding optimal recovery schemes for a cluster with n computers corresponds to the mathematical problem of finding the longest sequence of positive integers for which the sum of the sequence and the sums of all subsequences modulo n are unique.

  • 8.
    Laksman, Efraim
    et al.
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    Lennerstad, Håkan
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    Lundberg, Lars
    Blekinge Institute of Technology, School of Computing.
    Optimal computer crash performance precaution2012In: Discrete Mathematics and Theoretical Computer Science, ISSN 1462-7264, Vol. 14, no 1, p. 55-68Article in journal (Refereed)
    Abstract [en]

    For a parallel computer system withmidentical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use optimal allocation on m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then, what is the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time of the same parallel program? We denote the maximal ratio of completion times f(r, m) - i.e., the ratio for worst-case programs. In the paper we establish upper and lower bounds of the worst-case cost function f(r, m) and characterize worst-case programs.

  • 9. Laksman, Efraim
    et al.
    Lennerstad, Håkan
    Nilsson, Magnus
    Bounding the minimal Euclidean distance for any PSK block codes of alphabet size 82009Conference paper (Refereed)
    Abstract [en]

    We consider a bound for the minimal Euclidean distance of any PSK block code with eight symbols. The main result was established in [6] - here we prove that the bound is in fact stronger than was proven there. The bound is deduced by generalizing Elias' method of a critical sphere. It is not asympthotic, as previous Elias' sphere bounds, but valid for any specific word length and code size. Many known codes fulfil the bound with equality, proving the sharpness of the bound for these parameter values as well as the optimality of these codes.

  • 10.
    Laksman, Efraim
    et al.
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    Lennerstad, Håkan
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    Nilsson, Magnus
    Generalized upper bounds on the minimum distance of PSK block codes2015In: IMA Journal of Mathematical Control and Information, ISSN 0265-0754, E-ISSN 1471-6887, Vol. 32, no 2, p. 305-327Article, review/survey (Refereed)
    Abstract [en]

    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.

  • 11. Laksman, Efraim
    et al.
    Lennerstad, Håkan
    Nilsson, Magnus
    Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization2010In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 310, no 22 Special issue SI, p. 3267-3275Article in journal (Refereed)
    Abstract [en]

    The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size | C |. For q = 8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean. The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q = 8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and | C |. This is true for many multilevel codes.

  • 12. Laksman, Efraim
    et al.
    Lennerstad, Håkan
    Nilsson, Magnus
    Inner Distance Measure Bounds on the Minimal Euclidean Distance for Symmetric PSK Block Codes2009Conference paper (Refereed)
    Abstract [en]

    The minimum Euclidean distance is a fundamental quantity for block-coded PSK. In this paper improvements are made of bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size |C|. Earlier work, where the restriction q=8 was used, is continued by a generalisation allowing any q. The bound generalizes Elias critical sphere argument, which localizes the optimization problem to one neighbourhood, by use of so called inner distance measure for defining the shape of a sphere. Remark that codes which fulfill the bound with equality exist, and are best possible in terms of minimum Euclidean distance, for given parameters q, n and |C|.

  • 13. Lennerstad, Håkan
    An evolutionary textbook evolving by student activity2007In: Journal of Online Mathematics and its Applications, ISSN 1935-6439 , Vol. 7, no JuneArticle in journal (Refereed)
    Abstract [en]

    Successful education requires that the teacher has two knowledge competencies. The teacher not only needs to be familiar with the subject knowledge, it is also essential that the teacher have a realistic, detailed and practical knowledge of the students' understanding of the subject. This second kind of knowledge concerns the students' typical understanding and misunderstanding of the subject, and ways to handle them. It also includes ways to communicate meaning and interest in the subject--not to idealized students, but to real students. This paper describes a Swedish project that opens a channel allowing a teacher to systematically develop this knowledge while helping students. Teacher-student dialogues are conducted through a web page. As a result of the underlying goal, the project also extends the students' role in their education to a more responsible one. The textbook author uses the students' opinions and work at the web page to improve the book for the benefit of future students. Thus, the textbook evolves to be better adapted to the environment for which it is intended: studies by students. We present empiric results for an undergraduate distance course in calculus with 20 students.

  • 14. Lennerstad, Håkan
    Commensurable and rational triangles2007Report (Other academic)
    Abstract [en]

    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.

  • 15. Lennerstad, Håkan
    Envariabelanalys, idéer och kalkyler2005Book (Other academic)
  • 16.
    Lennerstad, Håkan
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    Local Linear Time Convergence of a Primal-Dual Energy Minimization Algorithm for Parallel Processing2014Conference paper (Refereed)
    Abstract [en]

    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.

  • 17. Lennerstad, Håkan
    Logical graphs: how to map mathematics1996In: ZDM - Zentralblatt für Didaktik der Mathematik, ISSN 0044-4103, Vol. 27, no 3, p. 87-92Article in journal (Refereed)
    Abstract [en]

    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.

  • 18.
    Lennerstad, Håkan
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Science.
    Matematikens dubbelnatur –undflyende innehåll,självtillräckligt språk2005In: Utbildning och Demokrati, ISSN 1102-6472, E-ISSN 2001-7316, Vol. 14, no 2, p. 27-55Article in journal (Refereed)
    Abstract [en]

    This article discusses the role in mathematics of its formal language, here called Mathematish. This language became significant when symbolic mathematics gradually replaced rhetoric mathematics. Mathematics gained in efficiency and calculation became dominant. It is claimed that this happened on the expense of mathematical interpretation, except for those who intuitively understand Mathematish. It is also claimed by linguistic arguments that the structure of a language isnaturally non-articulated for intuitive learners, often teachers, while teaching requires articulation. Languages are often excluding. Therelationship between content and language in mathematics is described from several viewpoints. Three distinct types of mathematical knowl-edge are suggested: 1. How to successfully use Mathematish rules, 2. Mathematish rules (computer programmable grammar), 3. Ideas and meanings of mathematics, e.g. applications and metaphors. Non-formal ways of hinting mathematical ideas and meanings, shedding light on both Mathematish and content, are suggested.

  • 19.
    Lennerstad, Håkan
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    Spectrums of knowledge types: mathematics, mathematics education and praxis knowledge2008In: Proceedings of MADIF6, Swedish Society for Research in Mathematics Education , 2008Conference paper (Refereed)
    Abstract [en]

    Knowledge in different research paradigms is discussed: mathematics, mathematics education and a paradigm of practical knowledge. I argue that the three paradigms as highly distinct, different and important. They try to cope with entirely different types of knowledge, all highly relevant for mathematics teachers.

    While mathematics is deductive and mathematical education is evidence based, practical knowledge is a type of knowledge that professionals in any profession develop by experience and by exchange with other professionals. It is based on experience more than on written text. It is well known that it to a large extent is difficult to articulate. Such knowledge is also essential in important types of mathematical knowledge. We discuss the role played by vagueness in mathematics. We also discuss linguistic mathematics knowledge which typically is present but mostly unformulated, as the mother tongue.

    I argue that mathematics, pedagogy and mathematics education suffers from drawbacks by being strongly rooted in the positivist tradition, in which knowledge can always be expressed in words – otherwise it is not knowledge. Central aspects of teacher’s day-to-day profession are too complicated to be captured in words. However, work has been done to allow such practical knowledge to be formulated among professionals. I would like to sketch a more fluent cooperation between the paradigms, in which the advantages of all the different knowledge types may interact and become increasingly useful to each other.

    For such an idea to reach reality, an efficient meeting form is needed. The Dialogue Seminar is developed precisely to study and communicate difficult-to-articulate practical knowledge among experienced professionals from different areas, using analogue and metaphor as catalysts. This offers mathematicians, mathematics education researchers, mathematics teachers and teacher students, and others, an excellent opportunity to listen in depth to each other, and to have a dialogue. 

  • 20. Lennerstad, Håkan
    The directional display1997Conference paper (Refereed)
    Abstract [en]

    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.

  • 21.
    Lennerstad, Håkan
    Blekinge Institute of Technology, Department of Telecommunications and Mathematics.
    The Geometry of the Directional Display1996Report (Refereed)
    Abstract [en]

    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.

  • 22.
    Lennerstad, Håkan
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    The n -dimensional Stern-Brocot tree2019In: International Journal of Number Theory, ISSN 1793-0421, Vol. 15, no 6, p. 1219-1236Article in journal (Refereed)
    Abstract [en]

    This paper generalizes the Stern-Brocot tree to a tree that consists of all sequences of n coprime positive integers. As for n = 2, each sequence P is the sum of a specific set of other coprime sequences, its Stern-Brocot set B(P), where |B(P)| is the degree of P. With an orthonormal base as the root, the tree defines a fast iterative structure on the set of distinct directions in ℤ+n and a multiresolution partition of S+n-1. Basic proofs rely on a matrix representation of each coprime sequence, where the Stern-Brocot set forms the matrix columns. This induces a finitely generated submonoid SB(n, ℕ) of SL(n, ℕ), and a unimodular multidimensional continued fraction algorithm, also generalizing n = 2. It turns out that the n-dimensional subtree starting with a sequence P is isomorphic to the entire |B(P)|-dimensional tree. This allows basic combinatorial properties to be established. It turns out that also in this multidimensional version, Fibonacci-type sequences have maximal sequence sum in each generation. © 2019 World Scientific Publishing Company.

  • 23.
    Lennerstad, Håkan
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    The n-dimensional Stern-Brocot tree2012Report (Other academic)
    Abstract [en]

    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.

  • 24. Lennerstad, Håkan
    et al.
    Bergsten, Christer
    Matematiska språk2008Collection (editor) (Other academic)
    Abstract [sv]

    Sju författare från olika områden ger sin syn på frågan om matematikens språk. Det är matematikerna Christer Kiselman och Håkan Lennerstad, didaktikerna Christer Bergsten och Madeleine Löwing, lingvisten Östen Dahl, och Bo Göranzon och Lars Mouwitz som är forskare inom forskningsområdet yrkeskunnande och teknologi.

  • 25.
    Lennerstad, Håkan
    et al.
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    Eriksson, Mattias
    Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
    List graphs and distance-consistent node labelings2018In: Electronic Journal of Graph Theory and Applications, ISSN 2338-2287, Vol. 6, no 1, p. 152-165Article in journal (Refereed)
    Abstract [en]

    In this paper we consider node labelings c of an undirected connected graph G = (V,E) with labels (1, 2, ...,|V|), which induce a list distance c(u, v) = |c(v) - c(u)| besides the usual graph distance d(u, v). Our main aim is to find a labeling c so c(u; v) is as close to d(u, v) as possible. For any graph we specify algorithms to find a distance-consistent labeling, which is a labeling c that minimize Σ u,vεV (c(u, v) - d(u, v))2. Such labeliings may provide structure for very large graphs. Furthermore, we define a labeling c fulfilling d(u1, v1) &lt; d(u2, v2) ) c(u1, v1) ⇒ c(u2, v2) for all node pairs u1; v1 and u2; v2 as a list labeling, and a graph that has a list labeling is a list graph. We prove that list graphs exist for all n = |V| and all k = |E|: n - 1 ≤ k ≤ n(n - 1)/2, and establish basic properties. List graphs are Hamiltonian, and show weak versions of properties of path graphs. © 2018 Indonesian Combinatorics Society.

  • 26. Lennerstad, Håkan
    et al.
    Jogréus, Claes
    Serier och transformer2002Book (Other academic)
  • 27. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    An Optimal Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems1995In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 24, no 4, p. 751-764Article in journal (Refereed)
    Abstract [en]

    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.

  • 28. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems1992Report (Other academic)
    Abstract [en]

    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.

  • 29. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Combinatorics for multiprocessor scheduling optimization and other contexts in computer architecture1996Conference paper (Refereed)
    Abstract [en]

    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.

  • 30. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Decomposing rational numbers2010In: Acta Arithmetica, ISSN 0065-1036, E-ISSN 1730-6264, Vol. 145, no 3, p. 213-220Article in journal (Refereed)
  • 31. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    En annan addition och Stern-Brocots träd2006In: Nämnaren : tidskrift för matematikundervisning, ISSN 0348-2723, no 3, p. 45-48Article in journal (Refereed)
    Abstract [sv]

    När två bråk adderas så adderar man bråkens täljare för sig och nämnare för sig. Så får man väl inte göra? Jodå, det får man, men inte med vanlig addition. Här får vi en glimt av vad följderna blir av denna annorlunda addition.

  • 32.
    Lennerstad, Håkan
    et al.
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    Lundberg, Lars
    Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering.
    Generalizations of the floor and ceiling functions using the Stern-Brocot tree2006Report (Refereed)
    Abstract [en]

    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.

  • 33. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling2007In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 35, no 2, p. 135-151Article in journal (Refereed)
    Abstract [en]

    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.

  • 34. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems2000In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, p. 1816-1838Article in journal (Refereed)
    Abstract [en]

    For the execution of an arbitrary parallel program P, consisting of a set of processes with any executable interprocess dependency structure, 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 [GRAPHICS] 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. Overhead for synchronization and reallocation is neglected only. We further present a tight bound which exploits a priori knowledge of the class of parallel programs intended for the multiprocessors, thus resulting in a sharper bound. The function g(n, k, u, q) is the above maximum taken over all parallel programs consisting of n processes. The functions G and g can be used in various ways to obtain tight performance bounds, aiding in multiprocessor architecture decisions.

  • 35. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems1993Report (Other academic)
    Abstract [en]

    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.

  • 36. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Computer Combinatorics2003Book (Other academic)
  • 37. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Scheduling Results for Parallel Computing1994In: SIAM news, ISSN 1557-9573, Vol. 27, no 7Article in journal (Refereed)
    Abstract [en]

    The situation of having jobs of some kind which may be dependent, and having several possible executors of jobs, is a very common one and appears in very diverse contexts. Clearly some kind of scheduling is needed: who shall do what? Also one often wants to have it all done as quicky as possible. One central scheduling question is whether to allow transferring of jobs between executors. The antipoles here are allowing unlimited transferring, usually called dynamic allocation of jobs, and allowing no transferring, which is static allocation.

  • 38. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Scheduling Results for Parallel Computing1996In: Applications on advanced architecture computers / [ed] Astfalk, Greg, Philadelphia, USA: SIAM , 1996, p. 155-164Chapter in book (Refereed)
    Abstract [en]

    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.

  • 39. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Worst Case Formulas Comparing Cache Memory Associativity1995Report (Other academic)
    Abstract [en]

    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.

  • 40. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal worst case formulas comparing cache memory associativity2000In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, p. 872-905Article in journal (Refereed)
    Abstract [en]

    In this paper we derive a worst case formula comparing the number of cache hits for two different cache memories. From this various other bounds for cache memory performance may be derived. Consider an arbitrary program P which is to be executed on a computer with two alternative cache memories. The rst 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 derive an explicit formula for the ratio of the number of cache hits h(P, k, u) for a(k, u)-cache compared to a (1, q)-cache for a worst case program P. We assume that the mappings of the program variables to the cache blocks are optimal. The formula quantifies the ratio [GRAPHICS] where the in mum is taken over all programs P with n variables. The formula is a function of the parameters n, k, u, and q only. Note that the quantity h ( P, k, u) is NP-hard. We assume the commonly used LRU (least recently used) replacement policy, that each variable can be stored in one memory block, and that each variable is free to be mapped to any set. Since the bound is decreasing in the parameter n, it is an optimal bound for all programs with at most n variables. The formula for cache hits allows us to derive optimal bounds comparing the access times for cache memories. The formula also gives bounds ( these are not optimal, however) for any other replacement policy, for direct-mapped versus set-associative caches, and for programs with variables larger than the cache memory blocks.

  • 41.
    Lennerstad, Håkan
    et al.
    Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
    Olteanu, Constanta
    Åtta IKT-projekt för matematiken i skolan: empiri och analys2012Report (Other (popular science, discussion, etc.))
    Abstract [en]

    Denna rapport presenterar empiri och analys av en granskning av åtta projekt som mottagit medel från Skolverket för att tillämpa IKT i skolans matematikundervisning. Empirin är organiserad enligt aktivitetsteorin, vilken sätter relationerna mellan människa, miljö, aktiviteter och mål i förgrunden. Empirin som presenteras är till stor del sammanställda repliker från lärare och elever vid intervjuerna, organi¬sera¬de för att belysa verksamhetens olika relationer. Det betyder att presentationen är till stor del på de verksammas villkor, och på deras språk. Ett stort antal konkreta slutsatser framkommer ur detta material. En av dem är att klass¬upp-sätt¬ningar av datorer är sällan framgångsrika, på grund av att teknisk support ofta var otillräcklig, och att lärarna inte kan veta hur mycket eleverna använder datorerna till icke-skol-verk¬sam¬het. Dessa problem finns inte för interaktiva skrivtavlor. De framstår däremot som ett socialt verktyg, som gör utbyte och dialog om ämnet lättare att få till stånd. I flera fall framkom indirekt, men ändå tydligt, att utbildningen på tekniken hade varit otillräcklig, trots att lärarna inte uttryckte ett tydligt missnöje med den. Skrivtavlan ökade lärarnas motivation för samarbete. En framåtriktad slutsats är att en lärargrupp som har ett fungerande samarbete och goda didaktiska, ämnesmässiga, ledar- och relationella kompe¬tenser med en interaktiv skrivtavla har en möjlighet att komma längre med elevernas måluppfyllelse.

  • 42. Lundberg, Lars
    et al.
    Klonowska, Kamilla
    Broberg, Magnus
    Lennerstad, Håkan
    Comparing the Optimal Performance of Multiprocessor Architectures2003Conference paper (Refereed)
    Abstract [en]

    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.

  • 43. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    An Optimal Lower Bound on the Maximal Speedup in Multiprocessors with Clusters1995Conference paper (Refereed)
    Abstract [en]

    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.

  • 44. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    An Optimal Upper Bound on the Minimal Completion Time in Distributed Supercomputing1994Conference paper (Refereed)
    Abstract [en]

    We first consider an MIMD multiprocessor configuration with n processors. A parallel program, consisting of n processes, is executed on this system-one process per processor. The program terminates when all processes are completed. Due to synchronizations, processes may be blocked waiting for events in other processes. Associated with the program is a parallel profile vector nu , index i (1<or=i<or=n) in this vector indicates the percentage of the total execution time when i processes are executing. We then consider a distributed MIMD supercomputer with k clusters, containing u processors each. The same parallel program, consisting of n processes, is executed on this system. Each process can only be executed by processors in the same cluster. Finding a schedule with minimal completion time in this case is NP-hard. We are interested in the gain of using n processors compared to using k clusters containing u processors each. The gain is defined by the ratio between the minimal completion time using processor clusters and the completion time using a schedule with one process per processor. We present the optimal upper bound for this ratio in the form of an analytical expression in n, nu , k and u. We also demonstrate how this result can be used when evaluating heuristic scheduling algorithms (12 Refs.)

  • 45. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Bounding the gain of changing the number of memory modules in shared memory multiprocessors1997In: Nordic Journal of Computing, ISSN 1236-6064, Vol. 4, no 3, p. 233-58Article in journal (Refereed)
    Abstract [en]

    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.

  • 46. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Combinatorics for Scheduling Optimization1996Conference paper (Refereed)
  • 47. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Comparing the optimal performance of different MIMD multiprocessor architectures1998Conference paper (Refereed)
    Abstract [en]

    We compare the performance of systems consisting of one large cluster containing q processors with systems where processors are grouped into k clusters containing u processors each. A parallel program, consisting of n processes, is executed on this system. Processes may be relocated between the processors in a cluster. They may,however not be relocated from one cluster to another. The performance criterion is the completion time of the parallel program. We present two functions: g(n,k,u,q) and G(k,u,q). Provided that we can find optimal or near optimal schedules,these functions put optimal upper bounds on the gain of using one cluster containing q processors compared to using k clusters containing u processors each. The function g(n,k,u,q) is valid for programs with n processes, whereas G(k,u,q) only depends on the two multiprocessor architectures. By evaluating g(n,k,u,q) and G(k,u,q) we show that the gain of increasing the cluster size from 1 to 2 and from 2 to 4 is relatively large. However, the gain of using clusters larger than 4 is very limited.

  • 48. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Global multiprocessor scheduling of aperiodic tasks using time-independent priorities2003Conference paper (Refereed)
    Abstract [en]

    We provide a constant time schedulability test for a 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 - root7 = 35.425%, the server can accept incoming aperiodic tasks and guarantee that the deadlines of all accepted tasks will be met. 35.425% utilization is also a threshold for a task to be characterized as heavy. The bound U-threshold = 3 - root7 approximate to 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor. For a server 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(m)(x) = 2(1-x)/(2+ root2+2x)+x/m. By using this function, the performance of the multiprocessor can in some cases be improved beyond U-threshold(m) by paying the extra overhead of monitoring the individual utilization of the current tasks.

  • 49. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Optimal bounds on the gain of permitting dynamic allocation of communication channels in distributed computing1999In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, p. 425-446Article in journal (Refereed)
    Abstract [en]

    Consider a distributed system consisting of n computers connected by a number of identical broadcast channels. All computers may receive messages from all channels. We distinguish between two kinds of systems: systems in which the computers may send on any channel (dynamic allocation) and system where the send port of each computer is statically allocated to a particular channel. A distributed task (application) is executed on the distributed system. A task performs execution as well as communication between its subtasks. We compare the completion time of the communication for such a task using dynamic allocation and k(d) channels with the completion time using static allocation and k(s) channels. Some distributed tasks will benefit very much from allowing dynamic allocation, whereas others will work fine with static allocation. In this paper we define optimal upper and lower bounds on the gain (or loss) of using dynamic allocation and k(d) channels compared to static allocation and k(s) channels. Our results show that, for some tasks, the gain of permitting dynamic allocation is substantial, e.g. when k(s) = k(d) = 3, there are tasks which will complete 1.89 times faster using dynamic allocation compared to using the best possible static allocation, but there are no tasks with a higher such ratio.

  • 50. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Slack-based Global Multiprocessor Scheduling of Aperiodic Tasks in Parallel Embedded Real-time Systems2008Conference paper (Refereed)
    Abstract [en]

    We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. Dhall's effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack - not on deadlines. We prove that if the load on the multiprocessor stays below (3 - √5)/2 ≈ 38.197%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of-the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%). ©2008 IEEE.

12 1 - 50 of 61
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf