Constraint Driven Communication Synthesis Alessandro Pinto Guoqiang Wang Mentors Luca Carloni 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 1 Outline Introduction Problem Definition Solving the Constrained Optimization Problem Algorithm and examples Conclusion and Future Work 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 2 Introduction A General System View 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 3 CCG 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 4 CCG G g V A A Comm Constraint Graph is a directed graph an abstract model used to specify comm requirements A vertex v associated to a port of computational module of the system A directed arc a representing a point to point comm channel btw two modules Arc Properties of a u v d a arc length distance btw u and v b a comm bandwidth on the constrained arc a 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 5 A Comm Library L L N A collection of comm links and comm nodes Link Properties d l link length distance the length of the longest comm channel that can be realized by this link b l link bandwidth the bandwidth of the fastest communication channel that can be realized by this link c l 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 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 6 Implementation 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 element 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 7 A path q v1 a1 v2 a2 vQ 1 aQ 1 vQ An alternating sequence of distinct vertices and arcs in a constraint graph G with V q G and A q G denoting respectively the set of vertices and arcs touched by q path properties length bandwidth cost 12 8 2001 d q i 0 d ai Q 1 b q min i 0 Q 1 b ai c q i 0 c ai Q 1 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 8 Arc Implementation Arc Matching iff corresponding to exactly one library link K way Arc Segmentation iff corresponding to the concatenation of K library links K way Arc Duplication iff corresponding to placing K library links in parallel 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 9 Examples of AI 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 10 Lemma For all Constraint graphs G g V A and all communication libraries L L N there exists an optimum point to point implementation graph with the minimum cost 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 11 Constraint driven comm synthesis problem To 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 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 12 Our Problem Given A Constraint Graph G g V A A Comm Library L L N Find The Optimum implementation graph with the minimum cost 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 13 Assumption on L Links that have better performance cost more l l L d l d l b l b l c l c l 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 14 Idea 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 UCP 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 15 Complex Solution Consider all the possible structures G G G 12 8 2001 G G Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation G 16 K way mergeability K arcs are mergeable is k way merge is the minimumcost solution 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 17 Non mergeability Conditions Bandwidth limitation It has to be proved Conditions on relative positions of arcs 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 18 Simple case 2 way Merging 1 2 a vs a a a a a A if d a d a p u p u p v p v no mergeable 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 19 K way Merge Same Concept express every properties w r t one link Ak a1 a2 ak A k 1 d ai d a p u p u p v p v n 1 k n i n n 1 k n i n i n i Ak M k 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 20 Bandwidth Condition intuition a1 a2 a3 ak G G We need Duplication to satisfy the bandwidth constraint 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation G r way merge plus k r way merge 21 Non 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 Ak a1 ak max b l min b u v b a i i j j 1 k l L i 1 k Ak M k 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 22 Non Mergeability Theorem for Relative Positions intuition Suppose that a cannot be merged with no other arcs in A What does it means A2 a A2 A2 M 2 What can we say about merging a with 2 arcs A3 a A3 M 3 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 23 Non 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 Ak 1 A a Ak 1 a M k h k A A 12 8 2001 h h h A a A a M Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 24 What we did so far Mergeability definition Non Mergeability Conditions Relative positions Bandwidth 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 25 Algorithm Generation of solutions set S Two matrixes Constrain Distance Sum Matrix Merging Distance Sum Matrix Merging and pruning conditions Calculate optimum comm Nodes position and cost of the solution Solution of the instance of Unite Covering Problem 12 8 2001 Alessandro Pinto Guoqiang Wang EE249 Final Project Presentation 26 Simple Example …
View Full Document
Unlocking...