221 Pages
English

Energy conscious on-chip communication bus synthesis and optimization for MPSoC architectures [Elektronische Ressource] / von Sujan Pandey

-

Gain access to the library to view online
Learn more

Description

EnergyConsciousOn-ChipCommunicationBusSynthesisandOptimizationforMPSoCArchitecturesVomFachbereich18ElektrotechnikundInformationstechnikderTechnischenUniversita¨tDarmstadtzurErlangungderWu¨rdeeinesDoktor–Ingenieurs(Dr.-Ing.)genehmigteDissertationvonM.Sc.SujanPandeygeboreninKathmandu,NepalReferent: Prof.Dr.Dr.h.c.mult.ManfredGlesnerKorreferent: Prof.Dr. Jo¨rgHenkelTagderEinreichung: 19.12.2006Tagdermu¨ndlichenPru¨fung: 15.06.2007D17Darmsta¨dterDissertationen2007AcknowledgmentsTherearesomanypeoplewhoactedasasource ofhelpandinspirationduringtheal-mostfouryearsoftimeandIoweadebtofthankstoallofthem. Inparticular,Iwouldlike to express my sincere gratitude to the thesis adviser Prof. Manfred Glesner, whogavemeanopportunitytoexploreaknowledgeinhisresearchinstituteandprovidedenormoussupportsandadvisestomaterializethisworkasathesis.IwouldalsoliketothankProf. Jo¨rgHenkelfromUniversityofKarlsruhe,Germany,for accepting asa reviewerof thisthesis and giving me anopportunity to visit himtodiscuss about the content. His comments and remarks were valuable to improve thequality of this thesis and to envision future new research directions. Furthermore, Iwould like to extend my thanks to Prof. Dimitris Pavlidis, Prof. Udo Schwalke, andProf. Ju¨rgenStenzelasmembersofexaminationcommittee. Inthiscontext,mysincerethanksto Prof. Schwalke for havingafruitful discussiononthe technological aspects.

Subjects

Informations

Published by
Published 01 January 2007
Reads 19
Language English
Document size 1 MB

EnergyConsciousOn-ChipCommunication
BusSynthesisandOptimizationforMPSoC
Architectures
VomFachbereich18
ElektrotechnikundInformationstechnik
derTechnischenUniversita¨tDarmstadt
zurErlangungderWu¨rdeeines
Doktor–Ingenieurs(Dr.-Ing.)
genehmigteDissertation
von
M.Sc.
SujanPandey
geboreninKathmandu,Nepal
Referent: Prof.Dr.Dr.h.c.mult.ManfredGlesner
Korreferent: Prof.Dr. Jo¨rgHenkel
TagderEinreichung: 19.12.2006
Tagdermu¨ndlichenPru¨fung: 15.06.2007
D17
Darmsta¨dterDissertationen
2007Acknowledgments
Therearesomanypeoplewhoactedasasource ofhelpandinspirationduringtheal-
mostfouryearsoftimeandIoweadebtofthankstoallofthem. Inparticular,Iwould
like to express my sincere gratitude to the thesis adviser Prof. Manfred Glesner, who
gavemeanopportunitytoexploreaknowledgeinhisresearchinstituteandprovided
enormoussupportsandadvisestomaterializethisworkasathesis.
IwouldalsoliketothankProf. Jo¨rgHenkelfromUniversityofKarlsruhe,Germany,
for accepting asa reviewerof thisthesis and giving me anopportunity to visit himto
discuss about the content. His comments and remarks were valuable to improve the
quality of this thesis and to envision future new research directions. Furthermore, I
would like to extend my thanks to Prof. Dimitris Pavlidis, Prof. Udo Schwalke, and
Prof. Ju¨rgenStenzelasmembersofexaminationcommittee. Inthiscontext,mysincere
thanksto Prof. Schwalke for havingafruitful discussiononthe technological aspects.
His comments and remarks were also equally valuable to improve the quality of this
work.
Ihadhadlotsofopportunity tointeractanddiscusswithcolleagueswithinthein-
stitute. Theirconstantsupportswerearesultofmysuccessinthiscarrier. Especially,I
wouldliketothankTudorA.MurganandLeandroS.Indrusiakbeinggoodcolleagues
as well as friends. Further, I can not forget friendly colleagues Heiko Hinkelmann,
Oliver Soffke, Oana Cobianu, Hao Wang, Petru Bacinschi, Massoud Momeni, Andre
Guntoro, and Hans-Peter Keil. As part of the scientific management, I would like to
extendmythankstoThomasHollstein,whohelpedmealotfromthemomentIsetmy
footinDarmstadttotheendofmystay. Inthisregard,IalsothanktoPeterZipfforhis
contributionfromadministrationofGKtolecturesandthescientificdiscussions.
I am equally indebted to the secretaries of institute, Silvia Hermann and Imgrid
Wackermann,whohelpedmeformanytinyproblems. Further,withoutawellrunning
system, I would not be able to carry out research and write my thesis. Thus, I would
liketothankAndreasSchmidtforhisvaluablesupports.
It is my such a pleasure to be around with good friends from school to university
andIamveryproudtohavethem. Especially,IthanktoDavidBerner,notonlyforcor-
rectingmyEnglish,butalsoforgivingmeadvicesandsuggestionswhenIwasinneed.
I would also like to thank Binod Uprety for his constant inspiration. Furthermore, it
iii
is difficult for me here to mention all good friends from my school, if their names are
not listed, I assured that my gratitude is not less than for those listed below. Espe-
cially,IthanktoKishorPoudel,LavaP.Kuikel,ShivaC.Maharjan,andBishnuUprety
withwhomIsharedallmostmytime. IwouldalsoliketothankNareshParajulifrom
KathmanduUniversity,whoalwaysencouragedmeasagoodfriend.
Attheend,Iwouldliketoexpressmysinceregratitudetomyparents. Theteaching
and guidance of my parents and the constant encouragement of my brother Sajan are
the mainsources of inspiration. Here, I cannot forget to mentionmy Manana ”Kalu”
foreverythingthatshehasdevotedforme.
SujanPandey
18July2007,Bremen,Germany.Kurzfassung
Heutzutage kann manin demEntwurf moderner System-On-Chips zweiwesentliche
Beobachtungen anstellen: Zum einen fu¨hrt die zunehmende Systemkomplexita¨t zu
einemsteilenAnstiegdesDatenverkehrsderBusarchitekturenaufdemChip. Zuman-
deren bewirkt die Technologieskalierung, dass Verbindungsleitungen immer du¨nner
und somit Laufzeitverzo¨gerungen immer gro¨ßer werden. Diese beiden Nebeneffekte
deuten darauf hin, dass der Entwurf von on-chip Datenbusarchitekturen auf dem
Chip eine immer gro¨ßer werdende Herausforderung fu¨r Systemdesigner wird. Das
Ziel dieser Arbeit ist daher, Algorithmen zur Synthese von energieeffizienten on-chip
Datenbussen zu entwickeln. Durch die Optimierung der Anzahl der Busse, der Bus-
breite und der Betriebsspannungen sind diese Algorithmen in der Lage, sowohl die
Chipfla¨chealsauchdieLeistungsaufnahmederDatenbussezuverringern.
Eine der Annahmen, die fu¨r die Synthese gemacht werden, ist, dass das betre-
ffende System bereits vollsta¨ndig partitioniert worden ist und diese Partitionen auf
geeignete Module eines Multiprozessor System-on-Chips (MPSoC) abgbildet worden
sind. Basierend auf diesen Modulen wird ein Task-Graph erstellt, der den Daten-
verkehr zwischen den on-chip Modulen modelliert. Die Problemformulierung des
Syntheseverfahrens wird unterteilt in Scheduling, Allocation und Binding. Eine kor-
rekte Formulierung dieserProbleme kanndannmitHilfevonOptimierungswerkzeu-
gen gelo¨st werden, welche die optimale Anzahl von Bussen und deren Breite bestim-
men. AufgrundderfortlaufendenSkalierungderBauelementeundVerbindungsleitun-
gen kann eine immer gro¨ßere Anzahl an Transistoren auf dem Chip integriert wer-
den. Dies fu¨hrt zu einer Zunahme der Leistungsaufnahme pro Fla¨cheneinheit, was
wiederum eine verminderte Gera¨tezuverla¨ssigkeit und Systemperformanz zur Folge
hat. Es ist daher wesentlich, die Leistungsaufnahme wa¨hrend der Bussynthese zu
beru¨cksichtigen. Eine der Hauptbeitra¨ge dieser Arbeit ist die Entwicklung eines Ver-
fahrens, das eine gleichzeitige Datenbussynthese und Spannungsskalierung zula¨sst
unddabeieinenKompromisszwischenKosten(d.h. AnzahlundBreite)fu¨rdieBusstr-
uktur und der Leistungsaufnahme eingeht. Die unbenutzte Zeit zwischen Kommu-
nikationsaufgabenwirddabeigenutzt,umdenBuszuteilenunddieBetriebsspannun-
genherunterzuregeln. DadieTechnikderkontinuierlichenSpannungsskalierungeine
ideale Charakteristik fu¨r die Leistungsaufnahme erzeugt, kann sie nicht fu¨r den Dig-
iiiiv
italentwurf mit aufwendigen Spannungsreglern eingesetzt werden. Um dieses Prob-
lemzuumgehen,wirdeinheuristischesVerfahrenfu¨rdiediskreteSpannungsregelung
entwickelt,dasinpolynomialerZeitkomplexita¨tdurchgefu¨hrtwerdenkann.
Ineinemechtzeit-eingebettetemSystemistderzuu¨bertragendeDatenverkehrzwis-
chen on-chip Modulen aufgrund der Vielfalt der Anwendungen nicht konstant. Des
weiteren wird der Einfluss von Prozessparametervariationen auf die Systemperfor-
manz mit zunehmender Technologieskalierung immer sta¨rker. Um die Effekte, die
von dem variablen Datenvolumen und der Prozessparametervariationen herru¨hren,
zu integrieren, wird in dieser Arbeit ein erweitertes Verfahren fu¨r die Bussynthese
vorgeschlagen. DaserweiterteVerfahrenfu¨hrtdiegleichzeiteBussysntheseundSpan-
nungsskalierung aus, allerdings unter Beru¨cksichtung des variablen Datenvolumens
und der zufa¨lligen Prozessvariationen im worst-case Fall. Simulationen, die anhand
voneinemautomatischerzeugtenBenchmarkundeinerrealenAnwendungdurchgef-
u¨hrt wurden, zeigen, dass eine intelligente Spannungsregelung wa¨hrend der Bussyn-
these sowohl die dynamische Leistungsaufnahme und die Leistungsaufnahme auf-
grundvonLeckstro¨menverringertalsauchdieAuswirkungenvonProzesstoleranzen
mildert.Abstract
Twomajortrendscanbeobservedinmodernsystem-on-chipdesign: firstthegrowing
trend insystemcomplexity resultsinasharpincreaseofcommunicationtraffic onthe
on-chip communication bus architectures. The second trend in technology scaling in-
dicatesthatthewiresaregettingthinnerandresultsinincrementofwiredelay. These
trends, taken together, designing on-chip communication bus architectures is becom-
inganevermore challengingtask forsystem designers. Thus, the aimofthis thesisis
to explore several algorithms that synthesize energy efficient on-chip communication
buses. Thealgorithmsreducechipsizeandpowerconsumptionbyoptimizingthebus
widths,thenumberofbuses,andthevoltagelevels.
Anassumptionforsynthesisisthatasystemhasbeenpartitionedandmappedonto
the appropriate modules of a multiprocessor system-on-chip (MPSoC) architecture.
Based on the partitioned and mapped modules, a communication task graph is ex-
tracted to modelcommunication betweenon-chip communicating modules. The syn-
thesis approach is formulated as scheduling, allocation, and binding problems. Once
correctly formulated, these problems are solved with the help of an optimization tool
to find the optimal bus width and the number of buses. As the device geometry and
thewiresarescaleddown,agrowingnumberoftransistorscanbeintegratedonasin-
glechip,whichleadstoanincreaseinpowerconsumptionperunitarea. This,inturn,
resultsinthedegradationofbothdevicereliabilityandsystemperformance. Thus,itis
essentialtooptimizebusenergyconsumption duringthesynthesisofcommunication
buses. As a major contribution, this thesis proposes a simultaneous on-chip commu-
nication bus synthesis and voltage scaling technique, that finds a trade-off between
communication bus cost (bus width and number of buses) and energy consumption.
The slack of each communication task is exploited in order to share communication
bus usage and to scale down the bus operating voltages. As the continuous voltage
scaling technique delivers an ideal energy consumption characteristics, it cannot be
applied for the digital design due to the expensive voltage regulators. To cope with
thisproblem,a heuristicfordiscrete voltage scalingtechniqueisproposed, whichcan
besolvedinpolynomialtimecomplexity.
Inareal-timeembeddedsystem,the amountofdatatobetransferred betweenon-
chip modules is not fixed over time. This is due to the diversity of applications that
vvi
run on a single chip. Furthermore, as the process technology is scaled down, the ef-
fectsofprocessvariationsarebecomingasignificantonsystemperformance. Inorder
to incorporate the combined effects of the data size and the process variations on the
performanceofcommunicationbuses,thisthesisproposesanextendedmodelforcom-
municationsynthesis. Theproposedmodelsimultaneouslyperformson-chipcommu-
nicationbussynthesisandvoltagescalingunderdatasizeandprocessvariations. The
problem is relaxed to a nonlinear optimization model, which synthesizes the optimal
bus widths and the number of buses considering worst case data traffic and process
variations. Theexperimentsconductedonanautomaticallygeneratedbenchmarkand
real-life applications show that applying voltage scaling during the synthesis of on-
chip communication buses effectively reduces dynamic power consumption, leakage
powerconsumption,andmitigatestheeffectsofprocessvariations.TableofContents
1 IntroductionandOverview 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 ResearchScopeandObjectives . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 ThesisOutline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 InfluentialFactorstothePerformanceofOn-ChipCommunicationBus 7
2.1 TechnologyScalingTrends . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 DeviceandWireScaling . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 EffectsofProcessVariations . . . . . . . . . . . . . . . . . . . . . . 11
2.2 LayoutRelatedFactors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 InterconnectPlanning . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 CombineRetimingandPartitioning . . . . . . . . . . . . . . . . . 16
2.2.3 BufferInsertionandWireWidthPlanning. . . . . . . . . . . . . . 18
2.3 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 CommunicationTopologies . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Bridges,Routers,andSwitches . . . . . . . . . . . . . . . . . . . . 23
2.3.3 GloballyAsynchronousandLocallySynchronous . . . . . . . . . 24
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 State-of-the-ArtinCommunicationBusSynthesisandOptimization 27
3.1 TransactionLevelCommunicationModeling . . . . . . . . . . . . . . . . 28
3.1.1 InterfaceRefinementandSynthesis . . . . . . . . . . . . . . . . . 29
3.1.2 TraceTransformationTechniquesBasedonKhanProcesses . . . . 32
3.1.3 AbstractChannelModel . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 BusCycleAccurateLevelSynthesis . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Real-timeConstraintDrivenSynthesis . . . . . . . . . . . . . . . . 37
3.2.2 LayoutandFloorplanAware . . . . . . . . . . . . . . . . . . . . . 45
3.3 PostSynthesisBusOptimization . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.1 Protocol Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
viiviii TABLE OF CONTENTS
3.3.2 OptimizationforLowPowerConsumption . . . . . . . . . . . . . 48
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 On-ChipCommunicationBusSynthesisandOptimization 53
4.1 TaskandArchitectureModels . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 DataProcessingTask . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.2 CommunicationTask . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 CommunicationTaskScheduling . . . . . . . . . . . . . . . . . . . . . . . 57
4.2.1 ProblemDefinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2.2 OptimalSolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2.1 MinimizingOCTsUnderReal-timeconstraints . . . . . 60
4.2.2.2 ExperimentalValidation . . . . . . . . . . . . . . . . . . 62
4.2.3 HeuristicMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.3.1 MinimizingOCTsUnderReal-timeConstraint . . . . . 64
4.2.3.2 ExtensionfortheDiversificationApproach . . . . . . . 73
4.2.3.3 EvaluationoftheHeuristic . . . . . . . . . . . . . . . . . 75
4.3 BusTopologySynthesisandOptimizationAlgorithm . . . . . . . . . . . 79
4.3.1 TopologySynthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 TopologyOptimization . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.2.1 IntermoduleCommunicationProfile . . . . . . . . . . . 81
4.3.2.2 CommunicationCost . . . . . . . . . . . . . . . . . . . . 82
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5 SimultaneousCommunicationBusSynthesisandVoltageScaling 87
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.1.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1.3 ComplexityAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2 CommunicationBusModel . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.3 CombinedBusSynthesisandSupplyVoltageScaling . . . . . . . . . . . 98
5.3.1 ContinuousVoltageScaling . . . . . . . . . . . . . . . . . . . . . . 98
5.3.2 DiscreteVoltageScaling . . . . . . . . . . . . . . . . . . . . . . . . 100
5.4 ExtensiontoBodyBiasing . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4.1 PowerDelayAnalysisw.r.tSupplyandBodyBiasVoltages . . . . 102
5.4.2 ContinuousVoltageScaling . . . . . . . . . . . . . . . . . . . . . . 105
5.4.3 DiscreteVoltageScaling . . . . . . . . . . . . . . . . . . . . . . . . 108
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109