A New Approach for Task Level Computational Resource Bi-Partitioning,Gang Wang, Wenrui Gong, Ryan Kastner Express Lab, Dept. of ECE, University of California, Santa Barbara,Overview,Resource Partitioning Problem Ant System (AS) Heuristic AS for Task Level Resource Partitioning Experiment Results Future Work,Resource Partitioning Problem(1),Heterogeneous architecture is getting more and more popular Partitioning problem is a fundamental challenge Automatically assign application onto different computation resources Optimizing system performance under constraints Two resource case : hardware/software co-design,Resource Partitioning Problem(2),NP-hard Different heuristic methods have been developed Simulated annealing Genetic Algorithms Tabu Search Expert System Kernighan/Lin,Overview,Resource Partitioning Problem Ant System (AS) Heuristic AS for Task Level Resource Partitioning Experiment Results Future Work,Ant System Heuristic (1),First introduced for optimization problems by Dorigo et. al. 1996 Inspired by ethological study on the behavior of ants Goss et. al. 1989 A meta heuristic A multi-agent cooperative searching method A new way for combining global/local heuristics,Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Ant System Heuristic (2),Key Observations,Autocatalytic effect Indirect communication (stigmergy) Ants deposit pheromones on the ground different the quality of the paths Pheromone trails encode a long-term global memory about the search process When the ants reach a decision, they are biased by the amount of pheromone (maybe probabilistically ),Overview,Resource Partitioning Problem Ant System (AS) Heuristic AS for Task Level Resource Partitioning Experiment Results Future Work,AS Algorithm for HW/SW Co-Design,Problem: For a given application, find the optimal resource partition under certain system constraints: Task level abstraction Task can map to GPP or Configurable Logic Pre-knowledge about the computational resources,Modeling the Task/Resource Partitioning Problem,Application is modeled as Task Graph (DAG) Sequential scheduling (not pipelined),Partitioning as Graph Bi-coloring,Task 1, 2, 7 and 8 are assigned to the GPP Task 3, 4, and 6 onto the configurable logic The inbound edges are colored accordingly We dont care the coloring for virtual nodes t0 and tn We dont care the coloring for edge e8n,Partitioning as Graph Bi-coloring,Each computing resource is assigned with a color ck Each edge eij is associated with a set of global heuristics (pheromone trails) ij(k) indicating the favorableness for tj to be colored with ck A coherent coloring is defined as: Each task node in the DAG is colored All the inbound edges of a task node have the same coloring as that of the corresponding task node,AS algorithm for resource partitioning (1),Initially, assign each of the edges in the task graph with a fixed pheromone 0 for both color c1 and c2, where c1 corresponds to GPP, while c2 for the configurable logic; Put m ants on t0; Each ant traverses the task graph to create a feasible bi-coloring solution si for the task graph, where i =1, . . . ,m; Evaluate all the m solutions. The quality of the solution s is measured by the overall execution time time(s). Among all solutions, find the best solution sbest which provides the minimum execution time and satisfies the configurable logic area constraint;,AS algorithm for resource partitioning (2),Update the pheromone for each color on the edges as follows: ij(k) (1 - )ij(k) + ij(k) (1) where : 0 1 is the evaporation ratio, escape from local minima k = 1 or 2, ij(k) =Q/time(sbest ) if eij is colored with ck in sbest 0 otherwise If the ending condition is reached, stop and report the best solution found. Otherwise go to step 2.,Step 3: How to construct individual coloring,Each ant traverses the graph in topologically sorted order Guarantees that each inbound edge to the current node has been already examined At each node, the ant will: Make guesses for the coloring of the successor nodes Make decision on the coloring of the current node,Make guesses for the successor task nodes,At task node ti, the ant makes guesses the coloring for each of the successor nodes tj : ij(k) : global heuristic on coloring tj with ck j(k) : local heuristic on coloring tj with ck,Make decision on the coloring of the current node,Upon entering a new task node ti, the ant makes a decision on the coloring of ti : probabilistically based on the guesses made by all the immediate precedents of ti Inbound edges are correspondingly colored once this decision is made,t,1,t,2,t,3,t,4,t,5,t,6,t,7,t,8,t,0,t,n,t,1,t,2,t,3,t,4,t,5,t,6,t,7,t,8,t,0,t,n,t,1,t,2,t,3,t,4,t,5,t,6,t,7,t,8,