Dynamic Task Allocation in Networks-on-Chip (WiMoA 2011 and ICCSEA 2011) Part 2

Solving the Region Selection Sub-problem (P3)

The main goal of this sub-problem is to select a near convex region of resources to minimize the external contention. The solution of problem P3 is same as [9].

Solving the Application Mapping Sub-problem (P4)

Here, the main goal is to map the application tasks in ACG to the resource locations in R, obtained from the solution of P3, such that the communication energy consumption can be minimized. In the proposed solution, if more than one node is eligible for mapping then, we will store them in an array in the ascending order of their life-time and will select the node having highest value of life-time for allocation. If the location found belongs to convex area of the region found in the solution for P3.

Fig. 4. The subtraction process during the region rotation process

Fig. 5. Region Rotation final solution into the current configuration using proposed and existing algorithms

Then that node is mapped onto that location. Otherwise, if all the possible locations for the selected node belongs to non-convex area of the region found in the solution for P3. Then we will repeat the location search for all lower life-time nodes, if they are sharing the locations found for the first node selected, then that node will be finally mapped onto the current system configuration.

Fig. 6.i illustrates the process of mapping the application ACG (see Fig. 6.i.(a)) onto a given region. As shown in Fig. 6.i.(a), the first vertex v4,which has the largest communication to its neighbors, is allocated to the center of the region. Next, vertices v7 and v8 are the candidate vertices for mapping, as both of them have the highest LT value, say v8 is chosen first. The location N2,0 is the only location fit for vg. Here N2io € Non_convex(N) then, before mapping vs onto N2,0, the probable locations (N2,0) for the lowest LT value node v5 among the nodes satisfying the criteria for mapping is found out. If the location found out is N2,0, then first the node v5 is mapped onto the location N2,0. This step is done to map the lowest LT value node onto the non-convex region of N, so that the cost of the new incoming application can be reduced.

Fig. 6. < i > Steps of Proposed Application Mapping Algorithm

Fig. 7. < ii> Existing Application Mapping Algorithm

In the existing solution v8 is mapped onto the best possible location N2,0, and lower LT value nodes onto the convex region of N. So, lower LT value nodes’ locations cannot be utilized efficiently by any other new incoming application.

Experimental Results

The Dynamic Task Allocator for Networks-on-chip is implemented using Java6. The existing and proposed methodology is applied to random applications and to real applications, i.e. the embedded system benchmark suite(E3S) [18]: Automobile/Industrial and Telecom. Three categories of random applications are generated with TGFF [19]. Each category contains 12 applications with the number of vertices in the ACG ranging from 8 to 12, the execution time of each node in the range of 1 to 11 clock ticks. For conducting the experiments, the value of a is taken to be 0.8 and that of 3 as 0.7. The three random categories are generated using the communication volume in the range of 10—110,100 — 1100,1000—11000. The experiments are conducted on a 8 x 8 homogeneous mesh-based NoC.

The proposed allocation policy, minimizes the average communication energy consumption compared to existing allocation policy, for all the three approaches (approach1, approach2, hybrid approach) in both the random and embedded system benchmark suits.

Table 1. Energy for Random Category

Table 2. Energy for ES Benchmark Suits

Conclusion

In this paper we proposed an alternative solution for dynamic allocation of tasks in NoC by incorporating a new parameter called Life-Time. Due to the inclusion of this new parameter, it enables us to deallocate a node when the Life-Time of the node expires. Due to the deallocation of a node, it minimizes the communication energy consumption of an application. But in case of existing allocation policy, a node belonging to a particular application is not deallocated till the whole application of completed [9]. In our allocation policy we use the information of Life-Time of a task and due to the consideration of the Life-Time information, after each allocation, the nodes having lower value of Life-Time contains more available neighbors, compared to the existing solution [9]. Since the node of lower value of Life-Time generally finishes early and deallocated, so the possibility of having more available neighbours for incoming tasks will be more and possibly get a better placement. From the experiment conducted, we have observed that the proposed solution is giving a better performance then the existing solution. The benefit of which can be realized with the increase in system load, where the proposed algorithm is successful in allocating resources to an application, whereas, the existing allocation policy may fail. This too helps in minimizing the communication energy consumed by the applications.