New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mozell Lind


Mozell Lind
Texas A&M
GPA 3.58


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 16 page Class Notes was uploaded by Mozell Lind on Wednesday October 21, 2015. The Class Notes belongs to CPSC 489 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 47 views. For similar materials see /class/226084/cpsc-489-texas-a-m-university in ComputerScienence at Texas A&M University.

Similar to CPSC 489 at Texas A&M

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15
Partitioning Ill Extended Partitioning for Embedded Applications MahapatraTexas AampMFallDO Binary partitioning Goal Map each node of a directed acyclic graph DAG to hardware or software binary choice and to determine the schedule for each node DAG The task level description of an application is specified as SDF synchronous data ow graph then SDF is translated to DAG representing precedence relationship among the nodes A DAG is input to partitioning tool Note For a given mapping ofa node hw or sw it is possible that the node can be implemented using various algorithms and synthesis mechanisms and they vary by area and delay outcomes Call this implementation bins MahapatraTexas AampMFallDO 2 Extended partitioning Goal Combine implementation bins with binary partitioning A joint problem of mapping nodes in DAG to hw or sw and within each mapping select suitable implementation for better results d r Imp39lmenta39 onbin Extended Panitiomng Hm wareSo ware Mapping and Scheduling geled on MahapatraTexas AampMFallDO 3 Assumptions 1 The precedences between the tasks are speci ed as a DAG G N A The throughput constraints on the SDF graph translates to a deadline constraint D Ie the execution time ofthe DAG should not exceed D clock cycles 2 Target architecture programmable processor and custom datapath These components have constraints 7 Software program and data size AS memory capacity Hardware has maximum size AH 3 Communication cost of interface ahwmm hardware area such as glue logic interface ascomm software area the code size for sendrec tcomm cycles to transfer data MahapatraTexas AampMFallDO 4 Assumptions 4 Selftimed blocking memory mapped interface 5 Communication cost of swsw and hwhw neglected 6 Area and time estimates of each node is known 7 Nodes mapped to the hw do not share resources MahapatraTexas AampMFallDO 5 Binary partitioning problem Given a DAG area and time estimates for hw and sw mapping of all nodes and communication cost subject to resource capacity constraints and deadline D determine for each node i the hw or sw mappingM and the start time for the execution of the node schedule ti such that the total area occupied by the nodes mapped to hardware is minimum MahapatraTexas AampMFallDO 6 Partitioning Algorithm with various notations Graph parameters G D ah asquot V size GCLPUAIgomh m Ammzmm constraints AHASahmmmas t Outputs Mi ti th 39software execution time estimate for node i size size of node I number of atomic operation MahapatraTexas AampMFallDO 7 Foundation Uses list scheduling serial traverse the node list to select a mapping that minimizes objective function Objective functions 7 Minimize finish time of the node or 7 minimize area of the node Note that use of one of the above objective at a time will lead to either reduced optimal or infeasible solutions the objective function should be adaptive at each node to determine the mapping and schedule The GCLP algorithm attempts this MahapatraTexas AampMFallDO 8 GCLP GC Global Criticality is a look ahead method that estimates time criticality of the algorithm If time is critical the objective function that minimizes nish time is selected else the one that minimizes area LP LP is a classi cation ofnodes based on their heterogeneity and intrinsic properties Each node is classi ed as extremity repeller or normal node A measure called local phase alelta quanti es the local mapping preferences of the node and update the threshold MahapatraTexas AampMFa1100 9 Mapping objective at each step Objectivel yv min nish u39me Global time criticality measure Weshld minresource use A Local Phase delta Phses 1 ex emlty Phaes 2 Repeller dal r 1 m no preerence pmpe es Phasesmmml measure MahapatraTexas AampMFa1100 10 GCLP owgraph 39S electNoder g Read Sel eqtmappiug time 11 mi times Mi M Y MahapatraTexas AampMFallDO 11 Global Criticality Estimates time criticality at each step in look ahead fashion At a given step the hwsw mapping and schedule of already mapped nodes is known m is determined on the basis of D and the schedule All the unmapped nodes are mapped to software and corresponding finish time T5 is computed If T5 exceeds D some of the unmapped nodes have to be moved from software to hardware to meet the deadline Define this to be the set NSAH The finish time TH is recomputed 7 GC is de ned here as fraction of unmapped nodes that have to be moved from software to hardware to meet the feasibility High GC many as yet unmapped nodes to be mapped to hw MahapatraTexas AampMFallDO 12 Illustration From Kalavade amp Lee s paper in Journal of Design Automation of Embedded System D W C271 5 N mm M Wm o muasmal may m m moved 1mm Schwam m havdwzm in mm mam n m Hmn u N ms maybe in Marmara m I m w Fignm 5 campuimun a Global Crillcnhly MahapatraTexas AXLMFallDO 13 GCLP Procedure Procedure Compute iGC M Mapped NM and Unmapped Nu nodes D IS th Size Vi E N Output GC Sl Find the the set NS H of unmapped nodes that have to be moved from software to hardware to meet the deadline D 811 Select a set of node in NU using a priority functionPf to move from software to hardware 1 2 Compute the actual finish time TH based on these NS H nodes being mapped to hardware 813 If T gtD goto 811 2 Calculate GC MahapatraTexas AXLMFallDO 14 GC procedure explaination Priority functionPf 7 rank the nodes in order of decreasing software execution time Is or 7 use ts th as function to rank the nodes greatest relative gain in time when moved to hardware BEST RESULT 7 rank in increasing order of ahi nodes with smaller hardware area are moved out of software rst The finish time is computed by an OOAlHND algorithm One can know if the set of nodes are feasible to move to hardware If not more nodes are required to move by repeating steps 11 to 13 GC is computed as a ratio of the sum of the sizes of the nodes in NSAH to the sum of the nodes in NU The size of a node is taken as number of elementary operations addmultiply etc in a node MahapatraTexas AampMFallDO 15 Local Phase LP classification Motivation 7 Nodes that consume disproportionately large amount of resource on one mapping compared to other are called extremities or LP 1 EX hardware extrerni re ujres a large area when mapped on to hardware but could be implemented inexpensively in software 39 The mapping preference of such nodes are quanti ed by extremity measure This measure modi es the threshold used in GC comparison Once feasible solutions are obtained it is possible to swap the nodes to reduce the hardware area The GCLP uses the concept of repeller or LP 2 nodes to perform on line swaps Need to look at nodal property EX bit level versus memory operations Node with bitops is software repeller 39 1 39 J 39 m1 F L39 J ofall repeller properties is expressed as repeller measure A mutiny r MahapatraTexas AampMFallDO 16 Extremity nodes and measure Bottleneck resources hardware gt area Software gt time Hardware extremity nodes and software extremity nodes Ei extremity measure that is used to modify the threshold to which GC is compared when selecting the mapping objective local phase delta for an extremity node 139 Procedure ComputeiExtremityiMeasure Ei for such nodes Input Isl ah VIEN 04 percentiles Output Elf l76 N 05 ltExlt05 Sl Compute the histograms of all the nodes with respect to their software execution time and hardware areas MahapatraTexas AampMFallDO 17 Extremity measurse SZ Determine Isx and ah that corresponds to wand percentiles of Is and ah histograms respectively S3 Classify nodes into software and hardware extremity sets Exs and Ex1 respectively if 052 ts0L and ahiltahB lE EXS software extremity if ahi 2 ahB and tsilt ts0L lE Exl1 hardware extremity S4 Determine the extremity value xi for node i ifiEEXsxi MahapatraTexas AampMFallDO 18 Threshold Modification Let GCk denotes the value at kth step when an extremity node 1 is to be mapped If Ei is ignored the threshold assumes its value of 05 Since GCk is averaged over all unmapped nodes mapping of node 1 in this case is based on GCk This leads to 7 Poor mapping Suppose node 1 is hardware extremity If GCk 2 05 Objl is selected minimum time and 1 could get mapped to hardware based on timecriticality However 1 is a hardware extremity and mapping it to hardware is obviously poor choice for P1 7 Infeasible mapping Suppose node 1 is software extremity If GCk lt 05 Obj2 is selected minimum area and 1 could get mapped to software Node 1 is a software extremity however mapping on to software could exceed the deadline MahapatraTexas AampMFallDO 19 Local Phase 2 Repeller Nodes The use of repellers to effect online swaps and reduce the overall hardware area There are several repeller properties Bitlevel instruction mix BLIM sw repeller Memory intensive instruction mix and lookup table instructions hw repeller MahapatraTexas AampMFallDO 20 Reading Assignments 1 Repeller measure procedure 0 2 GCLP algorithm MahapatraTexas AampMFallDO 21 GCLP Algorithm Stepl GC is computed as the given procedure Step2 set of ready nodes computed whose predecessors have been mapped Step3 selection of nodes are made from critical path step5 Since the execution time is unknown at this point effective execution time is determined here It is assumed that a node is mapped to hardware with probability GC and to software with probability lGC Step4 compute longest path based on the above effective execution time Step5 select a node from estimated critical path Step6 Mapping and schedule are determined 7 Use of extremityrepeller to modify the threshold Use of weight factors vary the extremityrepeller measures MahapatraTexas AampMFallDO 22 GCLP contd Obj Select a mapping that minimizes finish time of a node A node can begin execution only after all its predecessors have finished execution and data has transferred to it from predecessors Also node can not begin execution unless last node mapped to software has finished execution Obj2 uses percentage resource consumption measure It takes account of total cost of communication between node and its predecessors This favors the software allocation as algorithm proceeds MahapatraTexas AampMFallDO 23 Practical Examples 32KHZ 2PSK modem applications given in SDF in Ptolemy environment DAG is generated from SDF Nodes are at task level granularity carrier recovery time recovery equalizer descrambler etc 27 nodes See Fig 8 in the reference SDF Graph SDF39to DAG converter Area time estimates Silage code for each node Motorola 5600 Sm code for node ah ah MahapatraTexas AampMFallDO 24 GCLP Versus ILP Random graphs were selected Partitioned using GCLP algorithm ILP formulation was done using ILP solver CPLEX Refer table for comparison GCLP is within 30 of optimal solution Examples with more than 20 nodes could not be solved using ILP Using GCLP you can exceed 500 nodes MahapatraTexas AampMFallDO 25 Extended Partitioning Implementationbin curve revisited area t of implementation bins L W H time To minimize hardware area each node is to be mapped towards H subject to the deadline Extended partitioning is about to choose appropriate implementation bin and mapping for each node so as to yield minimum area and meet the deadline constraint Complex problem MahapatraTexas AampMFallDO 26 Designing Algorithm Guiding objectives Objective 1 complexity that scales reasonably 7 Binary partitioning has 2 Nl mapping possibilities for N nodes Given B implementation bins within a mapping extended partitioning problem has 2BlNl possibilities in the worstcase The algorithm complexity should not scale with dimensionality of partitioning process lNlZB Objective 2 Reuse of GCLP 7 Extended partitioning should decompose into two isolated steps such as mapping and bin selection Use GCLP for mapping 7 However optimization in isolation is ruled out as there is a correlation between implementation bin and mapping MahapatraTexas AampMFallDO 27 MIBS Heuristic Free Nodes N Ebrdput ahd scheiiul 39for free trades Seti leanar a m valu s Apply GCLP Mapping roi all free nodes Ssl39ecttaggmnode Twifh39mapping MT Find Implementaii nn bin fo r T within MT FreecfreeXT xedLeT u d ate schedule Mapping schedule imp1einentan39pn bins for all no es lNl times y MahapatraTexas AampMFallDO 28 MIBS Heuristic GCLP is used for mapping design objective 2 GCLP and bin selection are applied alternately within each step hence continuous feedback between mapping and implementation stages OON 3 BlNl2 where B is number of implementation bins per mapping scales polynomially design obj 2 MahapatraTexas AampMFallDO 29 Implementationbin selection Hardwaremapped In MIBS algorithm GCLP is applied each step to determine revised mapping of free nodes Let the free nodes mapped to hardware at the current step is free 1 nodes A tagged node is selected from free nodes Bin selection procedure Fixdnodes Free nodes Tagged noe T compute Bin fractionfEFCT Compute Bin Sensi vitthS SelectEin ET B MahapalraTexas AampMFallDO 30 Bin Selection Key Idea Use lookahead measure to correlate the implementation bin of the tagged node with the hardware area required for the free 1 nodes It selects most responsive bin in this respect as the implementation bin for the tagged node Assume that free 1 nodes can be either L or H bins Initially say H bins Now for each bin j of tagged node T compute the fraction of free 1 nodes that need to be moved from H bins to L bins in order to meet timing constraints BF 7 The bin fraction curve BFCT is the collection of the all bin fraction values of the tagged node T 0 LT k1 k HT MahapatraTexas AampMFa1100 31 Bin Selection Bin sensitivity is the gradient of BFCT It reflects the responsiveness of the bin fraction to the bin motion of node T Example If maximum slope of bin fraction is between kl and k moving the tagged node from bin kl to k will shift the largest fraction of free nodes to their L bins alternatively moving k to kl Will result largest reduction in area Hence select klth bin MahapatraTexas AampMFa1100 32


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.