Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 61
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1. Adolfsson, Vilhelm
    et al.
    Goldberg, Max
    Jawerth, Björna
    Lennerstad, Håkan
    Localized Galerkin Estimates for Boundary Integral Equations on Lipschitz Domanis1992Ingår i: SIAM Journal on Mathematical Analysis, Vol. 5, nr 23, s. 751-764Artikel i tidskrift (Refereegranskat)
    Abstract [sv]

    Galerkinmetoden studeras för att lösa ingegralekvationer med randvärden för Laplacepoperatorn för non-smooth områden. Konvergens visas med ett villkor på nätstorleken., vilket består av den lokala krökningen för approximerande områden. Feluppskattningar är härledda, och resultaten generaliserar för system av ekvationer.

  • 2.
    Klonowska, Kamilla
    et al.
    Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för programvarusystem.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    Lundberg, Lars
    Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för programvarusystem.
    Svahnberg, Charlie
    Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för programvarusystem.
    Optimal recovery schemes in fault tolerant distributed computing2005Ingår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 41, nr 6, s. 341-365Artikel i tidskrift (Refereegranskat)
    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 scheduling2009Ingår i: ACTA INFORMATICA, ISSN 0001-5903 , Vol. 46, nr 4, s. 285-295Artikel i tidskrift (Refereegranskat)
    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 Computing2003Konferensbidrag (Refereegranskat)
  • 5. Klonowska, Kamilla
    et al.
    Lundberg, Lars
    Lennerstad, Håkan
    Broberg, Magnus
    Comparing the optimal performance of parallel architectures2004Ingår i: Computer journal, ISSN 0010-4620, E-ISSN 1460-2067, Vol. 47, nr 5, s. 527-544Artikel i tidskrift (Refereegranskat)
    Abstract [sv]

    Vi betraktar ett parallellt program med n processer och synkroniseringsgranularitet z, samt två parallella arkitekturer. Det första har q processorer och full allokering av processerna är tillåten, och det andra har k processorer och ingen reallokering under körningen. Varje reallokering tar t sekunder. Vi definierar en funktion H(n,k,q,t,z) så att körtiden för ett program med n processer och granularitet z är högst en faktor H(n,k,q,t,z) längre för systemet utan reallokering än för systemed med. Vi antar optimal allokering av processer i de två systemen. Funktionen är optimal - det finns program där körtiden är exakt H(n,k,q,t,z) gånger längre. Resultaten valideras med mätningar på multiprocessorer i Sun/Solaris miljö.

  • 6. Klonowska, Kamilla
    et al.
    Lundberg, Lars
    Lennerstad, Håkan
    Svahnberg, Charlie
    Extended Golomb Rulers as the New Recovery Schemes in Distributed Dependable Computing2005Konferensbidrag (Refereegranskat)
    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 Computing2004Konferensbidrag (Refereegranskat)
    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 Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    Lundberg, Lars
    Blekinge Tekniska Högskola, Sektionen för datavetenskap och kommunikation.
    Optimal computer crash performance precaution2012Ingår i: Discrete Mathematics and Theoretical Computer Science, ISSN 1462-7264, Vol. 14, nr 1, s. 55-68Artikel i tidskrift (Refereegranskat)
    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 82009Konferensbidrag (Refereegranskat)
    Abstract [sv]

    Vi visar att en tidigare gräns för det minimala euklidiska avståndet för en block kod är starkare. Gränsen uppfylls med likhet av många kända koder, vilket visar att både koderna och gränsen är optimala för dessa parametervärden.

  • 10.
    Laksman, Efraim
    et al.
    Blekinge Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    Nilsson, Magnus
    Generalized upper bounds on the minimum distance of PSK block codes2015Ingår i: IMA Journal of Mathematical Control and Information, ISSN 0265-0754, E-ISSN 1471-6887, Vol. 32, nr 2, s. 305-327Artikel, forskningsöversikt (Refereegranskat)
    Abstract [sv]

    Detta papper generaliserar tidigare optimala övre gränser för minimala Euklidiska avståndet för fasskift block koder, s.k. phase shift keying (PSK). De är explicita i tre parametrar: alfabetstorlek, blocklängd och kodstorlek. Gränserna är framförallt generaliserade från koder över symmetrisk PSK till koder över asymmetrisk PSK men även till generell alfabetsstorlek. Block koder är även generaliserade i närvaro av annat brus än gaussiskt, vilket leder till icke-Euklidiska avståndsmått. I vissa fall ger asymmetrisk PSK högre Euklidiskt avstånd än symmetriskt med samma parametrar. Vi visar också att vissa kodklasser är optimala i gruppen av symmetrisk 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 optimization2010Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 310, nr 22 Special issue SI, s. 3267-3275Artikel i tidskrift (Refereegranskat)
    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 Codes2009Konferensbidrag (Refereegranskat)
    Abstract [sv]

    Minimala euklidiska avståndet är en fundamental storhet för en blockkod C. I detta papper görs förbättrade gränser för denna storhet som är explicita i de tre parametrarna alfabet storlek q, ordlängd n och kodstorlek c. Vi generaliserar Elias sfärargument genom att optimera ett inre avståndsmått så att vi får bästa tänkbara gräns för Euklidiskt avstånd.

  • 13. Lennerstad, Håkan
    An evolutionary textbook evolving by student activity2007Ingår i: Journal of Online Mathematics and its Applications, ISSN 1935-6439 , Vol. 7, nr JuneArtikel i tidskrift (Refereegranskat)
    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 triangles2007Rapport (Övrigt vetenskapligt)
    Abstract [sv]

    Man kan ställa sig frågan vad den liksidiga, halva kvadraten och de två gyllene trianglarna, med vinklar (π/5),((2π)/5),((2π)/5) och (π/5),(π/5),((3π)/5), har gemensamt. Ett svar är att vinklarna är kommensurabla med varandra - sådana trianglar kallar vi kommensurabla. Denna delklass av trianglar kan naturligt utrustas med en familjestruktur genom heltalstrippler som är hörnens relativa storlek, där den liksidiga är den enda medlemmen i den första generationen. En formel för antalet icke-likformiga trianglar som kan bildas av tre hörn i en regelbunden n-polygon härleds, som kan användas för att beräkna antalet kommesurabla trianglar i en generation. Tre "metatrianglar" beskrivs - där varje triangel är representerad av en punkt. Det visar sig att de rätvinkliga trianglarna bildar en höjd i en av metatrianglarna. Ögat är den punkt i en metatriangel som representerar metatriangeln själv. I andra delen av rapporten studeras trianglar genom sidlängd. En rationell triangel är en triangel där alla sidor och höjder är rationella tal. Vi visar att de räta rationella trianglarna är de Pythagoreiska, och de icke-räta består av två Pythagoreiska trianglar. Nästan alla trianglar är irrationella. Det visar sig att ingen Pythagoreisk triangel är kommensurabel. Vi visar att den enda triangel där vinklarna är kommensurabla och även sidorna kommensurabla är den liksidiga triangeln.

  • 15. Lennerstad, Håkan
    Envariabelanalys, idéer och kalkyler2005Bok (Övrigt vetenskapligt)
  • 16.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    Local Linear Time Convergence of a Primal-Dual Energy Minimization Algorithm for Parallel Processing2014Konferensbidrag (Refereegranskat)
    Abstract [sv]

    Pappret undersöker en energiminimiseringsalgoritm för en multiprocessor där processorns hastighet kan lokalt varieras för att minimera energin. För en open shop multiprocessor med n tasks och m maskiner studeras effektiviteten för en nyligen publicerad primal-dual algoritm. Nära optimium är dess komplexitet O(mn log(1/ε)) om n och m inte är lika och ε är datorns avrundningsfel. I pappret demonstreras hur linjarisering kan användas för att undersöka en algoritms komplexitet nära optimum. Vi visare också en uppskattning storleken för det område runt optimum där linjariseringsfelet är mindre än datorns avrundningsfel.

  • 17. Lennerstad, Håkan
    Logical graphs: how to map mathematics1996Ingår i: ZDM - Zentralblatt für Didaktik der Mathematik, ISSN 0044-4103, Vol. 27, nr 3, s. 87-92Artikel i tidskrift (Refereegranskat)
    Abstract [sv]

    En logisk graf är en form av riktad grad med vilken vilken matematisk teori eller bevis kan presenteras. Dess logik formuleras i grafform. Jämfört med en vanliga narrativa beskrivningen, vinner presentationen vanligen i överblick, klarhet och precision. Det huvudsakliga målet är didaktiskt: att göra det lättare för en läsare att orientera sig i en teori eller i ett bevis.

  • 18.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för matematik och naturvetenskap.
    Matematikens dubbelnatur –undflyende innehåll,självtillräckligt språk2005Ingår i: Utbildning och Demokrati, ISSN 1102-6472, E-ISSN 2001-7316, Vol. 14, nr 2, s. 27-55Artikel i tidskrift (Refereegranskat)
    Abstract [sv]

    Denna artikel behandlar på skilda sätt matematikens mest synliga och gripbara sida, dess formler, och spänningsförhållandet mellan formlerna och innehållet som de representerar. Detta spänningsfält är fundamentalt för matematikens filosofi såväl som för praktisk matematikundervisning. Hur når man elever? Med vilket språk? Tränger formelspråket ut det naturliga språket, berövas de aktiva sitt språk,förlorar de sitt tänkande och sin personliga frihet? Symbolspråket representerar tankeeffektivitet och uttrycker samtidigt matematikens generalitet, som kanske är matematikens mest karaktäristiska egenskap vid sidan av dess kvantitativa innehåll. I artikeln hävdas att denna språklighet har flera bieffekter i form av missuppfattningar om matematiken, som ger upphov till hinder för matematisk kommunikation. Det förefaller som lingvistisk analys kan spela en viktig roll för att förstå denna kommunikation. En relaterad fråga är vilka litterära former för matematikläroböcker som är effektiva. Ifrågasättande i dialogform kanske är särskilt viktigt i matematik, eftersom ämnet (naturligtvis) tål ifrågasättande och dessutom genom sin abstrakta och svårtillgängliga natur inbjuder till många typer av missförstånd. I sådana perspektiv kan både litteraturvetenskap och lingvistik vara vetenskaper som är besläktade med och viktiga för såväl matematiken som matematikdi-daktiken. De kan utgöra redskap i ambitionen att beskriva ett innehållpå andra sätt än med dess naturliga språk, bland annat för att indirekt karaktärisera detta språk. Det innebär en process som går utöver explicita kunskapsbegrepp och leder till poetiska/konstnärliga dimensioner.

  • 19.
    Lennerstad, Håkan
    Blekinge Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    Spectrums of knowledge types: mathematics, mathematics education and praxis knowledge2008Ingår i: Proceedings of MADIF6, Swedish Society for Research in Mathematics Education , 2008Konferensbidrag (Refereegranskat)
    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 display1997Konferensbidrag (Refereegranskat)
    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 Tekniska Högskola, Institutionen för telekommunikation och matematik.
    The Geometry of the Directional Display1996Rapport (Refereegranskat)
    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 Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    The n -dimensional Stern-Brocot tree2019Ingår i: International Journal of Number Theory, ISSN 1793-0421, Vol. 15, nr 6, s. 1219-1236Artikel i tidskrift (Refereegranskat)
    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 Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    The n-dimensional Stern-Brocot tree2012Rapport (Övrigt vetenskapligt)
    Abstract [sv]

    Stern-Brocots träd består av alla sekvenser (p₁, ...,p_{n}) av positiva heltal som saknar gemensam delare. De genereras gren för gren med vektoraddition, med en ON-bas som start, och kontrolleras av en generaliserad Euklidisk algoritm. Trädet inducerar en multiresolutionpartition av den första kvadranten av den (n-1)-dimensionella enhetssfären, vilket ger en riktningsapproximationsegenskap för en sekvens med dess föregångare i trädet. Två matrisrepresentationer presenteras, i båda innehåller matrisen alla föräldrar till en sekvens. Från en av dem följer isomorfismen av ett delträd med ett helt träd vars dimension är antalet föräldrar av toppsekvensen i delträdet. En typ av Fibonaccisekvenser visar sig vara sekvenserna som har snabbast växande summa. Konstruktionen kan ses som ett n-dimensionellt kedjebråk, och den kan vara en inbjudan till fortsatt n-dimensionell talteori. Nyckelord: Stern-Brocots träd, relativt prima tal, Fibonaccital, multiresolution partition, ON-bas, kedjebråk, Minkowskis frågeteckenfunktion.

  • 24. Lennerstad, Håkan
    et al.
    Bergsten, Christer
    Matematiska språk2008Samlingsverk (redaktörskap) (Övrigt vetenskapligt)
    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 Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    Eriksson, Mattias
    Blekinge Tekniska Högskola, Fakulteten för teknikvetenskaper, Institutionen för matematik och naturvetenskap.
    List graphs and distance-consistent node labelings2018Ingår i: Electronic Journal of Graph Theory and Applications, ISSN 2338-2287, Vol. 6, nr 1, s. 152-165Artikel i tidskrift (Refereegranskat)
    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 transformer2002Bok (Övrigt vetenskapligt)
  • 27. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    An Optimal Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems1995Ingår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 24, nr 4, s. 751-764Artikel i tidskrift (Refereegranskat)
    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 Systems1992Rapport (Övrigt vetenskapligt)
    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 architecture1996Konferensbidrag (Refereegranskat)
    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 numbers2010Ingår i: Acta Arithmetica, ISSN 0065-1036, E-ISSN 1730-6264, Vol. 145, nr 3, s. 213-220Artikel i tidskrift (Refereegranskat)
  • 31. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    En annan addition och Stern-Brocots träd2006Ingår i: Nämnaren : tidskrift för matematikundervisning, ISSN 0348-2723, nr 3, s. 45-48Artikel i tidskrift (Refereegranskat)
    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 Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    Lundberg, Lars
    Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för programvarusystem.
    Generalizations of the floor and ceiling functions using the Stern-Brocot tree2006Rapport (Refereegranskat)
    Abstract [sv]

    Vi studerar ett fundamentalt talteoretiskt problem med många tillämpningar. Ett bråk a/b delas upp så jämnt som möjligt i en mängd av c delbråk där summan av nämnarna är a och summan av täljarna är b. Minimum av bråken generaliserar golvfunktionen av a/b och maximum generaliserar analogt takfunktionen. Vi definerar även max-min-skillnaden, som är noll om och endast om c är högst största gemensamam delaren av a och b. För större c kvantifierar denna funktion avståndet till delbarhet. Stern-Brocots träd används för att bevisa grundläggande egenskaper för de tre storheterna. Problemet har uppkommit vid en generalisering av 4/3-satsen i datorsystemteori.

  • 33. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling2007Ingår i: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 35, nr 2, s. 135-151Artikel i tidskrift (Refereegranskat)
    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 systems2000Ingår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, s. 1816-1838Artikel i tidskrift (Refereegranskat)
    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 Systems1993Rapport (Övrigt vetenskapligt)
    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 Combinatorics2003Bok (Övrigt vetenskapligt)
  • 37. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Scheduling Results for Parallel Computing1994Ingår i: SIAM news, ISSN 1557-9573, Vol. 27, nr 7Artikel i tidskrift (Refereegranskat)
    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 Computing1996Ingår i: Applications on advanced architecture computers / [ed] Astfalk, Greg, Philadelphia, USA: SIAM , 1996, s. 155-164Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [sv]

    Lastbalansering är en av många möjliga orsaker för låga prestanda på parallelldatorer. Var och en av de två extremerna för lastbalansering, statisk allokering och dynamisk allokering, har sina för- och nackdelar. Detta kapitel illustrerar förhållandet mellan dem.

  • 39. Lennerstad, Håkan
    et al.
    Lundberg, Lars
    Optimal Worst Case Formulas Comparing Cache Memory Associativity1995Rapport (Övrigt vetenskapligt)
    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 associativity2000Ingår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, s. 872-905Artikel i tidskrift (Refereegranskat)
    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 Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
    Olteanu, Constanta
    Åtta IKT-projekt för matematiken i skolan: empiri och analys2012Rapport (Övrig (populärvetenskap, debatt, mm))
    Abstract [sv]

    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 Architectures2003Konferensbidrag (Refereegranskat)
    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 Clusters1995Konferensbidrag (Refereegranskat)
    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 Supercomputing1994Konferensbidrag (Refereegranskat)
    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 multiprocessors1997Ingår i: Nordic Journal of Computing, ISSN 1236-6064, Vol. 4, nr 3, s. 233-58Artikel i tidskrift (Refereegranskat)
    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 Optimization1996Konferensbidrag (Refereegranskat)
  • 47. Lundberg, Lars
    et al.
    Lennerstad, Håkan
    Comparing the optimal performance of different MIMD multiprocessor architectures1998Konferensbidrag (Refereegranskat)
    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 priorities2003Konferensbidrag (Refereegranskat)
    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 computing1999Ingår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, s. 425-446Artikel i tidskrift (Refereegranskat)
    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 Systems2008Konferensbidrag (Refereegranskat)
    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 av 61
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf