12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation1Constraint-Driven Communication SynthesisAlessandro PintoGuoqiang WangMentors:Luca Carloni12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation2Outline• Introduction• Problem Definition• Solving the Constrained Optimization Problem• Algorithm and examples• Conclusion and Future Work12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation3IntroductionA General System View:12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation4CCG12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation5CCG: • A Comm. Constraint Graph, is a directed graph, an abstract model used to specify comm. requirements.• A vertex : associated to a port of computational module of the system.• A directed arc : representing a point-to-point comm. channel btw two modules.• Arc Properties of : arc length/distance btw and .: comm. bandwidth on the constrained arc .),( AVgG=),( vua=va)(ad)(abvua12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation6A Comm. Library• A collection of comm. links and comm. nodes. • Link Properties:: link length/distance: the length of the longest comm. channel that can be realized by this link.: link bandwidth: the bandwidth of the fastest communication channel that can be realized by this link.: link cost: the value of this link wrt to other links in the library based on an optimality criterion varying with the type of application.NLL∪=')(ld)(lc)(lb12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation7Implementation Graph• The realization of a comm. architecture satisfying the requirements specified by a constraint graph• Ports of the in the Constraints Graph are kept• For each arc in the constraint graph we have a path in the implementation graphü There is a set of new nodes in the implementation graph N’ that are instances of library elementsü Each arc in the implementation graph is an instance of a library element12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation8A path• An alternating sequence of distinct vertices and arcs in a constraint graph , with and denoting respectively the set of vertices and arcs touched by . • path properties: length: bandwidth:cost:),,,...,,,,(112211 QQQvavavavq−−=Gq),( GqV ),( GqA∑−==10)()(Qiiadqd∑−==10)()(Qiiacqc))((min)()1,...0( iQiabqb−==12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation9Arc Implementation • Arc Matching: iff corresponding to exactly one library link.• K-way Arc Segmentation: iffcorresponding to the concatenation of K library links.• K-way Arc Duplication: iff corresponding to placing K library links in parallel.12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation10Examples of AI12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation11Lemma• For all Constraint graphs and all communication libraries , there exists an optimum point-to-point implementation graph with the minimum cost.),( AVgG=NLL∪='12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation12Constraint-driven comm. synthesis problemTo find the comm. architecture satisfying all the constraints specified as comm. requirements on the channels, while minimizing a predefined cost function capturing an optimality criterion which must be defined for the specific application.12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation13Our Problem• Given: A Constraint Graph: A Comm. Library: • Find:The Optimum implementation graph with the minimum cost),( AVgG=NLL∪='12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation14Assumption on L• Links that have better performance cost more)'()()'()()'()(',lclclblbldldLll≤⇒≤∧≤∈12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation15Idea• How can we solve the problem?üGenerate all the solutions?• And then?üAsk to the mentors?• And then? Got the solution• I’m a Synthesis expert, if you give me all the possible solutions I can solve the problem as a UCP12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation16Complex Solution• Consider all the possible structuresGG’G’’G’’’G’’’’G’’’’’12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation17K-way mergeability• K arcs are mergeable is k-way merge is the minimumcost solution12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation18Non-mergeability Conditions• Bandwidth limitation üIt has to be proved• Conditions on relative positions of arcs12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation19Simple case: 2-way MergingmergeablenovpvpupupadadifAaa−⇒−+−≤+∈||)'()(||||)'()(||)'()(',vsaa’a a’1) 2)12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation20K-way Merge• Same Concept, express every properties w.r.t. one link{}kkinkninininknnikkMAvpvpupupadadkAaaaA∉⇒−+−≤+−⊆=∑∑≠∈≠∈ ],1[],1[21||)()(||||)()(||)()()1(...,,12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation21Bandwidth Condition (intuition)Ga1a2a3akG’We need Duplication to satisfy the bandwidth constraintG’r-way merge plus (k-r)-way merge12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation22Non-Mergeability Theorem for Bandwidth • Duplication is allowed only if there is no link in the common subpath the doesn’t share the implementation of some arcs {}{ }{ }kkkijikjLlikkMAvublbabaaA∉⇒+≥=∑=∈∈1],1[1),(min)(max)(,...,12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation23Non-Mergeability Theorem for Relative Positions (intuition)• Suppose that a cannot be merged with no other arcs in AüWhat does it means?üWhat can we say about merging a with 2 arcs?2222,, MAAaA ∉∈∀?333MAaA∈⊃12/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation24Non-Mergeability Theorem for Relative Positions• If a is not k-way mergeable with any set of k ark in A it is not k+1 mergeable with any set of k+1-arc in A{}{}(){ } { }( )hhhkkkMaAaAAAkhMaAaAA∉∪⊂∀∈∀⇒∉∪⊂∀−−,\|],|,[,\1112/8/2001Alessandro PintoGuoqiang WangEE249 Final Project Presentation25What we did so far• Mergeability definition• Non-Mergeability ConditionsüRelative
View Full Document
Unlocking...