Architecture synthesis for adaptive multiprocessor systems on chip [Elektronische Ressource] / von Harold Ishebabi

Harold Ishebabi

Sujets

• Informatik

Informations

• Publié par: universitat_potsdam
• Publié le: 01 janvier 2009
• Nombre de lectures: 19
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

DepartmentforComputerScience
ProfessorshipforEngineering
ArchitectureSynthesisfor
AdaptiveMultiprocessorSystemsonChip
Dissertation
zurErlangungdesakademischenGrades
“doctorrerumnaturalium”
(Dr.rer.nat.)
inderWissenschaftsdisziplin“TechnischeInformatik”
eingereichtander
Mathematisch-NaturwissenschaftlichenFakultat¨
derUniversitat¨ Potsdam
Von
HaroldIshebabi
Potsdam,den29.05.2009
1.Berichterstatter:Prof.Dr.rer.nat.ChristopheBobda
2.Prof.PaulChow
3.Prof.Dr.AachimRettbergThis work is licensed under a Creative Commons License:
Attribution - Noncommercial - Share Alike 3.0 Unported
To view a copy of this license visit
http://creativecommons.org/licenses/by-nc-sa/3.0/












































Published online at the
Institutional Repository of the University of Potsdam:
URL http://opus.kobv.de/ubp/volltexte/2010/4131/
URN urn:nbn:de:kobv:517-opus-41316
http://nbn-resolving.org/urn:nbn:de:kobv:517-opus-41316 Hiermit erklare¨ ich,dass dieArbeit ankeiner anderenHochschule eingereichtsowie selbstandig¨ und
nurmitdenangegebenenMittelnangefertigtwurde.
Potsdam,29.05.2009
(HaroldIshebabi)Abstract
This thesis presents methods for automated synthesis of flexible chip multiprocessor systems from
parallelprogramstargetedatFPGAstoexploitbothtask-levelparallelismandarchitecturecustomiza-
tion. Automated synthesis is necessitated by the complexity of the design space. A detailed descrip-
tion of the design space is provided in order to determine which parameters should be modeled to
facilitate automated synthesis by optimizing a cost function, the emphasis being placed on inclusive
modeling of parameters from application, architectural and physical subspaces, as well as their joint
coverage in order to avoid pre-constraining the design space. Given a parallel program and a set of
an IP library, the automated synthesis problem is to simultaneously (i) select processors (ii) map and
schedule tasks to them, and (iii) select one or several networks for inter-task communications such
that design constraints and optimization objectives are met. The research objective in this thesis is
to find a suitable model for automated synthesis, and to evaluate methods of using the model for ar-
chitectural optimizations. Our contributions are a holistic approach for the design of such systems,
corresponding models to facilitate automated synthesis, evaluation of optimization methods using
state of the art integer linear and answer set programming, as well as the development of synthesis
heuristicstosolveruntimechallenges.Acknowledgement
This thesis results from my research work at the Professorship for Computer Engineering of the
Institute of Computer Science of the University of Potsdam from 2007 to 2009. Many people have
contributed to this work or assisted me in one way or the other. While I cannot provide a full list in
thisshortacknowledgement,Iwouldliketoexplicitlythankafewindividuals.
Especially I would like to thank my advisor Prof. Dr. rer. nat. Christophe Bobda for the opportunity
to work in the emerging field of flexible Chip Multiprocessor Systems at his Professorship, for pro-
ductivediscussionsattheTechnicalUniversityofKaiserslauternthatultimatelyledtothiswork,and
forhisleadershipthroughoutmywork.
ManythankstoProf.PaulChowandProf.Dr.AachimRettbergfortheirinterestinmythesisandfor
expendingtheirinvaluabletimetoreviewmywork,andtoserveonmythesiscommittee.
IwouldliketoexpressmygratitudetoProf.Dr.TorstenSchaub,Dipl.-Inform.MartinGebser,Dipl.-
Inform.RolandKaminskiandDipl.-Inform.BenjaminKaufmannallattheProfessorshipforKnowl-
edge Processing and Information Systems for their support on Potassco suite for Answer Set Pro-
gramming,tocolleaguesDipl.-Ing.PhilippMahrforcoordinatingdevelopmentworkontheplatform
PinHat particularly when I was working from a great distance, to Manuela Zeitner for general orga-
nizational assistance, and to working students Dipl.-Inf. Christian Lorchner¨ and Oliver Matheis for
their collaboration on PinHat. Thanks also to Dr. Humphrey Rutagemwa for reviewing this thesis in
theearlystages,andtoDr.KizitoSsamulaMukasaforguidingmeinmanyways.
To my loving wife Alice thank you for your patience and support. To my parents and siblings, as
well as to my friends and former colleagues Dr. Konstantinos Nikitopoulos, Msc. Venkatesh Ra-
makrishnan,NeemaMukasa,ViliMulla,RamdeMamadou,RaimundDoerr,DeogratiasKirondeand
ElisabethBoettcher,thankyousomuchforyourmoralsupport.FinallytomycolleaguesatSpectrum
SignalProcessing:thankyouforbearingwithme.i
Contents
ListofFigures 1
ListofTables 3
ListofAlgorithms 5
1 Introduction 1
1.1 DesignPhasesforFlexibleCMPSystems . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 ResearchObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 ArchitectureOptimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 EfficiencyofaDesignFlow . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 MainContributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Organization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 DesignSpaceofCMPSystems 7
2.1 SystemArchitectureSubspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Peripherals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 ProcessingElements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 CommunicationInfrastructure . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 MemoryArchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 ApplicationSubspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 TaskMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Network-Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4 Reconfigurability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.5 ProgrammingParadigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 PhysicalSubspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 DesignSpaceExploration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1 ProcessorDesignandExploration . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.2 NoCDesignandExploration . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.3 CMPDesignToolsandMethodologies . . . . . . . . . . . . . . . . . . . . 22ii CONTENTS
2.5.4 MappingApplicationstoFixedCMP . . . . . . . . . . . . . . . . . . . . . 24
2.5.5 Domain-SpecificExploration. . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 ProblemFormulation 27
3.1 ProposedDesignFlowforFlexibleCMPSystems . . . . . . . . . . . . . . . . . . . 27
3.2 ILPFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 BasicFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.3 Makespan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.3 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4 SAT-BasedSynthesis 73
4.1 MethodsforSolvingSATProblems . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.1 TheResolutionProofSystemandtheDPAlgorithm . . . . . . . . . . . . . 73
4.1.2 TheDPLLAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2 AnswerSetProgrammingandthePotasscoSuite . . . . . . . . . . . . . . . . . . . 77
4.3 EncodingtheSynthesisProblemasASPPrograms . . . . . . . . . . . . . . . . . . 78
4.3.1 TaskMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.2 ProcessorSharing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.3AreaConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.4 NetworkUsage . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.5 NetworkCapacityandAreaConstraints . . . . . . . . . . . . . . . . . . . . 79
4.3.6 SchedulingConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.7 Makespan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.8 ObjectiveFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4 ComparisonofSynthesisResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4.1 Non-RealtimeApplications . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4.2 RealtimePreemptiveScheduling . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.3 MakespanOptimization . . . . . . . . . . .