Sage Journals: Discover world-class research

Abstract

This article presents the development of configurations for bio-inspired self-healing cellular arrays known as Embryonics (embryonic electronics). In the Embryonics design, the configurations are employed to define the functionality and connections of each cell. However, developing configurations of the Embryonics is a time-consuming and challenging work due to lack of effective tools. In this article, an approach is proposed to develop configurations using graphic mapping, which also optimizes the length of configurations for the Embryonics. Using metric embedding, the problem of configurations is exactly formulated to binary quadratic assignment problem and routing problem with constraint of the Embryonics architecture. Since binary quadratic assignment problem is nondeterministic polynomial-time hard, a genetic algorithm is used to tackle this problem for achieving high-quality placement. Due to the limitation of communication bandwidth, how to resolve congestion is also an important issue. An improved ant colony algorithm is presented to realize routing of the Embryonics based on the result of placement. Configurations of the Embryonics are formed according to the result of placement and routing. Experimental result on a $4 \times 4$ multiplier demonstrates that developing configurations for lookup table–based Embryonics using graphic mapping can lower the difficulty of the Embryonics design and optimize placement and routing of Embryonics.

Keywords

Embryonics reliability metric embedding placement and routing

Introduction

The reliability of electronic systems has always been an issue with electronic engineering. Common ways to improve the reliability, such as dual modular redundancy and triple modular redundancy, usually have high resource overhead and poor fault-coverage.¹ Embryonics (embryonic electronics) is a promising alternative to design highly robust integrated circuits.^2,3 It aims to make the digital hardware obtain some of the features of biological organisms such as self-replication and self-repair. However, designing an Embryonics system is a hard job due to lack of computer-aided design (CAD) tools. In its present state, Embryonics is usually implemented using field programmable gate array (FPGA). It synthesizes and simulates using FPGA design software such as Xilinx ISE Foundation. However, the early stages of designing Embryonics have to specify the function and connectivity of each cell by hand. This process is also called development of configurations for the Embryonics. In many cases, designers have an approximate idea of the Embryonics architecture and cell structure but little information about the specific function of each cell and the interconnections between cells. These make the development of configurations be a challenging and time-consuming task, especially in complex applications. Moreover, it is prone to increase the length of configurations determined by hand, which means to increase hardware overhead. Therefore, a design tool is needed to help designers develop the configurations for the Embryonics.

In the early stage of the Embryonics, the implementation of the Embryonics is based on the MUXTREE architecture.³ The function of each cell is a multiplexer with two inputs and one output, and the connectivity between cells is limited. Thus, a digital circuit can be converted into multiplexer networks via ordered binary decision diagrams. A genetic algorithm is used to define the functionality and connectivity of cells by mapping a multiplexer network into a MUXTREE Embryonics.⁴ With the development of electronic technique, most implementation of the Embryonics is based on lookup table (LUT) architecture^5,6 at the present time. In LUT-based Embryonics, the function of each cell has a LUT which has four or six inputs and one output, and the number of data lines connecting cells to each other is large. It is hard to develop configurations of LUT-based Embryonics using the method applied by Ortega-Sanchez et al.⁴

In the design of a LUT-based Embryonics, a specific application can be represented to a task graph according to various function modules predefined by the Embryonics. Then, the functionality of cells is defined by mapping a task graph into the architecture of the Embryonics using concepts from graph embedding and metric geometry.⁷ The connectivity between cells can be also defined by routing path allocation based on the placement. Thus, configurations of the Embryonics can be developed by means of placement and routing.

The placement of the Embryonics is similar to the one in FPGA and networks-on-chip (NoC). There exist quite a multitude of approaches for placement, such as simulated annealing,⁸ StarPlace,⁹ and HeAP.¹⁰ Analytical placement using graph mapping shows significant scalability for the large design compared to traditional simulated annealing–based placement methods. Convex assigned placement for regular integrated circuit (CAPRI) is used as a global optimization step to produce a good initial placement using graph embedding concepts to accurately model routing architectures during FPGA placement.¹¹ An architecture-aware analytic mapping (A3MAP) algorithm has been proposed for NoC placement with homogeneous and heterogeneous cores on regular and irregular mesh or custom architecture. The task mapping problem is solved by two effective heuristics, a successive relaxation algorithm to achieve short runtime for mapping and a genetic algorithm to achieve high mapping quality.¹² However, in the Embryonics, some cells such as input cells have specific structure to deal with additional signals. The input nodes in the task graph are required to map to the input cells in the Embryonics. Therefore, an application mapping algorithm should tackle these requirements during the placement of Embryonics.

Based on the placement, the routing, which also exists in the FPGA design flow, is used to determine the communication path among cells. Due to the constraint of communication bandwidth in the Embryonics, how to resolve congestion is the most important issue. A simple iterative maze-running technique¹³ is presented to improve the quality of wiring around congested areas by ripping up and rerouting every net in every iteration. A breadth-first search is used to perform routes in a random order. In the face of failures, a penalty factor is introduced to select the routes which need to be ripped up.¹⁴ A coarse graph expansion has been used to address the issue of scare routing resources by considering the side effects that the routing of one connection has on another.¹⁵ If some connections are not able to be achieved, individual connections would be removed and rerouted to resolve routing conflicts. In essence, the schemes of ripping up and retrying are a key factor to avoid congestion during routing. The success of a route is dependent not just on the choice of which nets to reroute but also on the order that the rerouting is done.¹⁶

In this article, an approach is presented to develop configurations determining the function and connectivity of cells in the Embryonics by means of placement and routing. Our approach is divided into two steps. In the step of the placement, an interconnection matrix is first developed to model application task graph according to function modules. Then, an analytic distance metric of Embryonics architecture is constructed in terms of the shortest links between any two cells. Next, based on matrix projections, the application task graph is embedded to the metric space in order to minimize the total links on Embryonics and ensure routability simultaneously. The objective of this step is to find a permutation matrix representing a valid placement which meets the constraint of communication bandwidth on the Embryonics. In the step of the routing, a ripping up and retrying scheme for congested areas is applied. Also, a heuristic algorithm with a penalty function is used to implement the routing based on the placement. A routable net will be achieved through multiple iterations of this algorithm.

The remainder of this article is organized as follows: section “Embryonics architecture and design flow” introduces the architecture and a typical design flow of the Embryonics; section “Model of graphic mapping” describes the model of graphic mapping based on task graph and architecture graph; section “Problem formulation” formulates the placement to assignment problem using metric embedding and defines the constraint of the routing; in section “Implement issues,” a genetic algorithm and an improved ant colony algorithm (IACA) are proposed as the efficient solutions for the mapping problem; in section “Experimental results,” a $4 \times 4$ binary multiplier is implemented to demonstrate the feasibility of developing configurations of the Embryonics by graphic mapping; and, finally, the conclusion is presented in section “Conclusions and future work.”

Embryonics architecture and design flow

Architecture of Embryonics

Figure 1 shows a standard architecture of the Embryonics consisting of a matrix of X by Y cells which are divided into two categories: work cells (depicted in white) and spare cells (depicted in gray). Because the role of spare cell is not important for developing configurations, it has been left out in this article. The cell in the rest of this article represents work cell. Each cell stores configurations (also called DNA) of the Embryonics and executes different subsets of DNA called gene according to its X and Y coordinates which are identified by their positions in the array. The gene defines the functionality and connectivity of the cell. The cells are interconnected through a NEWS network (North-East-West-South connections) making each cell connect to adjacent cells merely. This means that a long-distance connection needs to pass multiple cellular input/output (I/O) router to accomplish the connections. An application is performed by cells cooperated with each other in the array. Therefore, each cell needs to carry out certain function and transmit the result to other cells. In addition, each cell is able to detect errors by itself. When a failure in a cell is detected, the self-repair process is activated, and the fault cell will be replaced by a space cell, so that the overall function of the original array is preserved.

Figure 1.

Overview of the (a) Embryonics architecture and (b) cell block diagram.

It is worth mentioning that for the ease of design of the cells, the first row and the last row of the Embryonics usually have an additional multiplexer to select input signals. Thus, the functional unit in these cells is a bit different from other cells. More information about the Embryonics architecture can be found in Mange et al.³ and Seffrin and Biedermann.¹⁷

Design flow of an Embryonics

Similar to the design flow of a MUXTREE Embryonics,⁴ the following steps are necessary to design a LUT-based Embryonics:

Step 1: Define the type of functions implemented by cells;

Step 2: Specify the application as a set of functions with communication between them;

Step 3: Construct a task graph from the description;

Step 4: Place the task graph into the Embryonics;

Step 5: Route the Embryonics based on the placement;

Step 6: Generate configurations of the Embryonics by determining the function and connectivity of each cell;

Step 7: Design the Embryonics according to configurations;

Step 8: Synthesize and simulate the design by FPGA design tools.

Steps 1–5 of the design have to be developed by hand. Due to the constraint of communication bandwidth, steps 4 and 5 are the most challenging and time-consuming. This article develops an automatic algorithm for steps 4 and 5.

Model of graphic mapping

Step 4 in the design of an Embryonics is implemented by graphic mapping which is viewed as an embedding of a graph representing an application into a designed metric space representing the architecture of the Embryonics. Figure 2 shows the system model of the graphic mapping.

Figure 2.

System model of graphic mapping: (a) task graph and (b) architecture graph.

Task graph for an application

According to functions defined by the cells of the Embryonics, an application is specified as a collection of functions with communication between them. It is modeled as a directed graph called task graph $Q = (V, E)$ as shown in Figure 2(a). It starts from the input nodes and terminates when the output nodes issue the result. Each node $v_{i} \in V$ represents a function of the application with a unique ID between 1 and $n$ marked in the upper right of the node. A directed edge $e_{i, j} \in E$ represents that node $v_{i}$ receives an input from node $v_{j}$ with $vol (e_{i, j})$ representing communication volume between $v_{i}$ and $v_{j}$ .

Architecture graph for an Embryonics

A regular mesh directed graph called architecture graph $S = (C, L)$ is constructed to represent the Embryonics as shown in Figure 2(b). Each square box (depicted in white) in the graph corresponds to a cell in the Embryonics with a unique coordinate. Each cell $c_{i} \in C$ is also uniquely identified by an integer $i$ (depicted in light gray) called the cell ID which is a one-to-one correspondence with the cell coordinate. Each directed edge $l_{i, j} \in L$ represents directed data line between $c_{i}$ and $c_{j}$ transferring the results from $c_{i}$ to $c_{j}$ . $bw (l_{i, j})$ represents the communication bandwidth between $c_{i}$ and $c_{j}$ shown by a number on the directed edge. The cells (depicted in dotted box) in the first and the last rows are used to deal with input and output signals, respectively.

Graphic mapping model

The graphic mapping model is developed based on task graph and architecture graph. For ease of the design, we assume that (a) the number of nodes in the task graph is equal to the number of cells in the architecture graph and (b) the nodes dealing with input and output signals (e.g. nodes 1 and 13) are assigned to the first and the last rows in architecture graph, respectively.

The graphic mapping model is constructed to obtain a placement matrix which aims to minimize the total connections of the embedding and ensure the routability. In the graphic mapping model, an interconnection matrix is first developed to model task graph. According to a graph-drawing technique¹⁸ using distance matrices, an analytic distance metric representing the architecture graph is then constructed in terms of the minimal links between any two cells. Next, based on matrix projections, the interconnection matrix is embedded to the metric space of the architecture graph in order to minimize the total connections. In order to ensure the routability, the graphic mapping must satisfy the constraint of communication bandwidth. The result of the placement is a permutation matrix.

Problem formulation

The formulation of the placement is in the form of an assignment problem. The quality of placement influences the quality of routing. The higher the quality of placement, the more achievable the routing will be. The formulation of the routing, which implements interconnections between cells with adjacent connections, is to control routing congestion based on the placement. Based on the interconnection matrix of the task graph and the permutation matrix, a matrix representing the interconnections between cells after the placement is obtained. The matrix contains the information about adjacent connections and long-distance connections. The routing is to find an interconnection matrix containing only adjacent connections and satisfy communication bandwidth in the architecture graph.

Formulation of placement

According to the task graph, a $n \times n$ interconnection matrix $M_{t}$ is constructed,⁵ where $M_{t} (i, j)$ is equal to $vol (e_{i, j})$ as shown in Figure 3. Each row of $M_{t}$ represents interconnections between a node and all other nodes in the task graph. The $M_{t}$ encapsulates interconnection relations for the entire task graph and represents the metric space of the task graph.

Figure 3.

Interconnection matrix of a task graph.

As stated previously, the placement problem is equivalent to determine the assignment of the node ID to the cell ID. This assignment can be mathematically represented by an $n \times n$ permutation matrix $P$ . The row indices and the column indices in $P$ represent the node ID and the cell ID, respectively. For example, if $P (k, i) = 1$ , then the node $k$ is assigned to the cell $i$ . According to the hypothesis of the graphic mapping model, only one element in each row and each column of $P$ is set to 1; all others must be 0. The action of $P$ on the task graph is represented by $D_{p} = P^{T} M_{t} P$ , which represents the interconnection of nodes on the architecture graph after placement. For instance, if $D_{p} = 2$ , then the cell $i$ connects to the cell $j$ with communication volume of 2. In addition, according to the hypothesis (b) of the mapping model, some nodes dealing with the input or output signals, represented as set $G$ in the task graph, are required to assign to some specific cells represented as set $H$ in the architecture graph.

According to the one-to-one correspondence between the cell ID and the cell coordinate, the minimal links between two cells are calculated by the cell coordinates in case no faulty cell exits, as shown in equation (1)

D_{d} (i, j) = d_{row} (c_{i}, c_{j}) + d_{col} (c_{i}, c_{j})

(1)

where $d_{row} (c_{i}, c_{j})$ and $d_{col} (c_{i}, c_{j})$ represent horizontal links and vertical links between cells $c_{i}$ and $c_{j}$ , respectively. Since architecture graph is a regular mesh architecture, $d_{row} (c_{i}, c_{j})$ and $d_{col} (c_{i}, c_{j})$ are calculated by the coordinate of cells. For example, if the cell coordinate of cell $c_{3}$ is (1, 3) and the cell coordinate of cell $c_{5}$ is (2, 1), the minimal links $D_{d} (3, 5) = | 1 - 2 | + | 3 - 1 |$ . Thus, distance matrix $D_{d}$ contains the minimal links of any two cells for an entire architecture graph and represents the distance metric space of the architecture graph.

Based on the permuted interconnection matrix $D_{p}$ and the distance matrix $D_{d}$ , the minimal links of the node $i$ to the node $j$ after placement can be calculated by $D_{p} (i, j) \times D_{d} (i, j)$ . Therefore, the placement problem is formulated mathematically to find a permutation matrix $P$ to minimize $f_{obj}$ as shown in the following equation

\begin{matrix} \min f_{obj} & = \sum_{i = 1}^{m} \sum_{j = 1}^{n} D_{p} (i, j) \times D_{d} (i, j) \\ D_{p} & = P^{T} M_{t} P \end{matrix}

(2)

In order to ensure the feasibility of routing, $D_{p}$ needs to satisfy $| P^{T} M_{t} P - M_{a} | \geq 0$ , where $M_{a}$ is an interconnection matrix representing the connections of the architecture graph. Thus, the constraints of the placement problem are shown as follows

| P^{T} M_{t} P - M_{a} | \geq 0

(3)

\sum_{i = 1}^{n} P (i, j) = 1, \forall j = 1, 2, \dots, n

(4)

\sum_{j = 1}^{n} P (i, j) = 1, \forall i = 1, 2, \dots, n

(5)

P (g, h) = 1, g \in G, h \in H

(6)

P (i, j) \in 0, 1

(7)

The constraints on the elements of $P$ restrict the solution space of our formulation to a nonconvex set. Thus, convex optimization techniques, such as gradient descent, are not suitable to be directly applied to solve this problem.¹² In fact, this type of formulation is known as binary quadratic assignment problem (BQAP) that is nondeterministic polynomial-time (NP)-hard.¹⁹ We address BQAP by a genetic algorithm with staged research. The detail of this approach is described in the subsequent section.

Formulation of routing

The object of routing is to find a legal set of paths that accomplishes the required interconnections between cells based on the placement. It is clear that small amount of total links obtained in the process of the placement will reduce the degree of routing congestion. A routing matrix satisfying communication bandwidth will be obtained based on a valid result of placement even if it is not the optimal result. Thus, a feasible connection will be accomplished by repeated iterations of a routing algorithm. In order to improve the quality of global wiring, a scheme of ripping up and retrying around congested area is needed.

Our overall routing methodology is a two-phase approach. In phase 1, the path with source cell and destination cell in one line will be routed directly in order to obtain the shortest path. Phase 2 is a routing for long-distance connections. Since the long-distance connections denoted in the permuted interconnection matrix $D_{p}$ cannot be routed directly on the architecture graph, they are needed to be divided into multiple adjacent connections. Thus, all long-distance connections are decomposed into adjacent connections and then routed with adjacent connections step by step in phase 2. When the routing is accomplished, $D_{p}$ is transformed into a routing matrix $M_{r}$ containing only adjacent connections. Similar to interconnection matrix $M_{t}$ for a task graph, a $n \times n$ interconnection matrix $M_{a}$ for an architecture graph is constructed. The $M_{a}$ contains adjacent connections for the entire architecture graph and represents the communication bandwidth in the architecture graph. The objective of the routing is to obtain a routing matrix $M_{r}$ to satisfy $M_{c} = | M_{a} - M_{r} | \geq 0$ . In other words, all elements $m_{i, j} \in M_{c}$ are no less than 0.

Implement issues

The process diagram of our approach implementing the placement and routing is shown in Figure 4. First, a genetic algorithm with staged research is applied to find a permutation matrix $P$ for the placement problem formulated in equation (2). Then, an IACA is presented to accomplish the routing based on the placement. The approach is repeated until there is no improvement for k-times iterations. Finally, a permutation matrix providing an optimized performance for the placement and a routing matrix are obtained.

Figure 4.

Main process diagram of our approach to implement placement and routing.

Genetic algorithm for placement

Equation (2) is in the form of a combinatorial optimization problem. A genetic algorithm is suitable to solve optimization problems.²⁰ A genetic algorithm is used to explore the design space efficiently for task assignment, mapping, and routing path allocation.²¹ The authors used a genetic algorithm to achieve high-quality mapping for NoC.¹² However, due to the constraints of equation (6), we need to select appropriate schemes which fit well in our BQAP formulation.

According to the binary constraints on the elements of permutation matrix $P$ , a valid $P$ can be achieved from multiple columns swapping in a given valid solution. In addition, since a node in the task graph cannot be assigned to any cell in the architecture graph, the schemes of encoding, crossover, and mutation in our genetic algorithm are required to make the columns of $P$ swap in the right scope. We use a specific dividing and merging rules to create an offspring. Algorithm 1 is the pseudo-code of our genetic algorithm for BQAP.

Encoding

Algorithm 1. Placement function ().
Input: $M_{t}$ : an interconnection matrix for task graph
$D_{d}$ : a distance matrix for the minimal links between any two cells.
Output: $P$ : an optimal permutation matrix.
$f_{obj}$ : the total connections between cells after placement.
begin
generate legal permutation matrix $P$ arbitrarily;
calculate $f_{obj}$ by Equation (2);
generate $parent 1$ by encoding matrix $P$ ;
while run times ≤k-times do
generate a valid $parent 2$ arbitrarily;
( $child 1$ , $child 2$ ) = crossover ( $parent 1$ , $parent 2$ );
( $child 1$ , $child 2$ ) = mutation ( $child 1$ , $child 2$ );
calculate $f_{obj}$ of $child 1$ and $child 2$ ;
$parent 1$ = minimum ( $child 1$ , $child 2$ );

$P$ is naturally coded as a string of integers called chromosome. For example, a $6 \times 6$ shown in Figure 5 is coded as $[365214]$ . In a chromosome, the number $q$ and its site $i$ represent $P (q, i) = 1$ . The encoding for a permutation matrix $P$ makes the operation of crossover and mutation be more subtle.

Figure 5.

Encoding for a permutation matrix $P$ .

Crossover

A crossover is to produce a new feasible solution with the good characteristics of parent chromosomes. Since some nodes in the task graph are required to assign to some specific cells in the architecture graph, the chromosomes are divided into substrings for crossover. Then, new chromosomes are constructed by the new substrings. An example of crossover is given below with two substrings, as shown in Figure 6. First, $parent 1$ is divided into two substrings $s 1$ and $s 2$ . Similarly, $parent 2$ is divided into $s 3$ and $s 4$ . Then, alleles between the first site to the random cross point in $s 3$ are copied to the first part of $s 1$ . Next, a new substring $o 1$ is produced after the repetitive alleles are removed. Similarly, $o 2$ , $o 3$ , and $o 4$ are produced in this way. Finally, $o 1$ and $o 2$ and $o 3$ and $o 4$ constitute $child 1$ and $child 2$ , respectively.

Figure 6.

Crossover of two chromosomes.

Mutation

A mutation operation is performed for each child. Similar to the operation of crossover, a child is divided into substrings. Then, two numbers in a substring randomly selected are swapped to generate a new substring. Then, the new substrings constitute a new child with two numbers swapped. The swapping is valid only if it reduces the number of the total links. After the mutation operation, one of the two children with the minimum links is chosen as the parent 1 for the next evolution.

IACA for routing

There are two types of connections, adjacent connections and long-distance connections, indicated by the permuted interconnection matrix $D_{p}$ after placement. For the adjacent connections, they are connected directly in our routing process because these are the shortest paths. The long-distance connections indicated in the permuted interconnection matrix $D_{p}$ comprise two types of connections. For the first type of connections, the source cell and the destination cell are nonadjacent but in the same row or in the same column. In our routing scheme, these long-distance connections are divided into adjacent connections in the same row or in the same column in order to minimize the total links of connections. These adjacent connections are the shortest paths for this type of long-distance connections. Thus, a new permuted interconnection matrix $D_{p}$ , which is the foundation of the subsequent routing, is obtained after routing these two types of connections.

For the second type of connections, the source cell and the destination cell are neither in the same rows nor in the same columns. Communication bandwidth makes the routing quite difficult. The difficulty in the routing increases as the complexity of the connections grows. Moreover, the connections interact with each other. It is hard to find proper paths for the connections manually or by an exhaust algorithm. Ant colony algorithm can search on several computational threads based on local information and global information on the quality of previously obtained result.^22,23 Thus, an IACA is used to realize the long-distance connections. It takes full advantage of prior information about the connections to find a promising solution. For a long-distance connection, the shortest distance between a source cell and a destination cell is fixed in case no faulty cell exits. Thus, the IACA is not used to find a shortest path but to search a suitable path which satisfies communication bandwidth.

Each ant has the coordinate of source cell $c_{s}$ and destination cell $c_{d}$ and moves from $c_{s}$ to $c_{d}$ by forwarding from one cell to the next one. It can only move along the closest direction to destination cell. The ants choose direction according to a probability which is a function of local pheromone trails. An ant located in cell $c_{i}$ uses pheromone $T_{ij}$ of cell $c_{j} \in {allowed}_{k}$ to compute the probability $p_{ij}^{k}$ of cell $c_{j}$ as next hop. The ant chooses the direction by $min_{j \in {allowed}_{k}} {p_{ij}}^{k}$ . The $p_{ij}^{k}$ is shown as follows

p_{ij}^{k} = (\begin{matrix} \frac{T_{ij}}{\sum_{s \in {allowed}_{k}} T_{is}} & j \in {allowed}_{k} \\ 0 & otherwise \end{matrix}

(8)

where ${allowed}_{k}$ is the allowed list of ant $k$ . The pheromone $T_{ij}$ , associated with the edge joining cells $c_{i}$ and $c_{j}$ , is updated as follows

T_{ij} = (1 - ρ) \cdot T_{ij} + \sum_{k = 1}^{m} Δ T_{ij}^{k}

(9)

where $ρ$ is the evaporation rate, $m$ is the number of ants, and $Δ T_{ij}^{k}$ is the quantity of pheromone laid on edge $(i, j)$ by ant $k$

Δ T_{ij}^{k} = (\begin{matrix} \frac{Φ}{L_{k}} & if ant k used edge (i, j) in its tour \\ 0 & otherwise \end{matrix}

(10)

where $Φ$ is a constant and $L_{k}$ is the length of the path constructed by ant $k$ .

For all long-distance connections, a colony of ants move from the source cells to the destination cells until all ants complete the tour. When all the long-distance connections are routed, a routing matrix is formed. The configurations for Embryonics are developed if $| M_{a} - M_{r} | \geq 0$ , if not the routing process is repeated. A penalty-pheromone $Δ T_{ij}^{co}$ is added to the congested areas to decrease the chances to be selected in a retrying routing process. The penalty-pheromone is given as follows

Δ T_{ij}^{co} = (\begin{matrix} \frac{1}{L_{co}} & if edge (i, j) belongs to the congested path \\ 0 & otherwise \end{matrix}

(11)

where $L_{co}$ is the length of the congested path for ant $k$ .

A requested routing matrix will be found by repeated iterations of the scheme of ripping up and retrying. In our algorithm, it may need many ants to find valid paths. Most of them find invalid paths and deposit pheromone trails on those paths, which increases the probability to find a valid path by a subsequent ant.

Experimental results

Implementing a Embryonics $4 \times 4$ multiplier

In order to demonstrate the development of configurations for LUT-based Embryonics, a universal $4 \times 4$ binary multiplication function with four inputs was built. This case also acts as the building block to construct any proportional–derivative (PD), proportional–integral (PI), or proportional–integral–derivative (PID) controller.^24,25 Although this is a relatively simple problem, it allows all of the basic concepts and functions of the development of configurations to be validated.

Figure 7 shows a $4 \times 4$ array multiplier with 4-bit inputs $X = x_{3} x_{2} x_{1} x_{0}$ and $Y = y_{3} y_{2} y_{1} y_{0}$ and 8-bit outputs $Z = z_{7} z_{6} z_{5} z_{4} z_{3} z_{2} z_{1} z_{0}$ . Figure 8 shows a task graph of the $4 \times 4$ array multiplier, where each logic-node has an ID. In the task graph, the logic-nodes with ID 1–8 implement two AND functions on inputs $X$ and $Y$ . The other logic-nodes realize a full adder function with 4-bit inputs and a carry output, a sum output. The implementation of this $4 \times 4$ multiplier requires 20 cells.

Figure 7.

Four-input $4 \times 4$ array multiplier.

Figure 8.

Task graph of a $4 \times 4$ multiplier.

We construct an Embryonics consisting of a matrix of 5 × 4 cells to implement the multiplier as shown in Figure 9, where 8 cells (in the first row and last row) with a multiplexer to select the input signals realize the AND function and 12 cells (rows 2–4) realize the full adder function. More information about the cell architecture can be found in Zhang et al.²⁶ Our program of placement and routing was run on MATLAB 7.0 in windows XP OS with dual-core CPU (3.00 GHz). The statistic results of routing are shown in Table 1 by executing IACA in this article and maze-running technique¹³ many times. An optimized configuration of a $4 \times 4$ multiplier is obtained as shown in Figure 9. Each cell has a unique title at the top of the box. The number in the title represents the corresponding logic-node in the task graph is placed to this cell. The directed lines represent the connections between the cells.

Table 1.

Summary and comparison of results on routing.

	Final steps	Used times (s)
Ant colony algorithm	72	5.384032
Maze-running technique	75	5.931325

Figure 9.

Optimized configuration of a $4 \times 4$ multiplier.

According to the result of configurations, synthesis and simulation of the $4 \times 4$ multiplier were carried out in Xilinx ISE Design Suite 13.2. Figure 10 shows the result of the multiplier implemented in an Embryonics. For instance, at the time of 557.699 ns, the 4-bit inputs are $X = 0111$ (the hexadecimal value is 7) and $Y = 0011$ (the hexadecimal value is 3) and the 8-bit output is $Z = 00010101$ (the hexadecimal value is 21). Table 2 presents a summary of hardware overhead and supply power obtained from running Xilinx ISE with Virtex-6 for the configuration both in Figure 9 and in Zhang et al.²⁶

Table 2.

Hardware overhead and supply power.

	Figure 9		Zhang et al.²⁶
	Used	Available	Used	Available
Number of slice registers	52	301,440	54	150,720
Number of slice LUTs	146	301,440	151	150,720
Supply power (W)	1.821		1.825

Figure 10.

Implementation of the $4 \times 4$ multiplier in an Embryonics.

Discussion

In some task graphs, the input and output signals of some logic-nodes are more than the communication bandwidth of the cells in architecture graph. In this case, the placement and routing cannot be accomplished. Thus, these logic-nodes should be divided into several sub-nodes where the input and output signals are less than the communication bandwidth of cells.

For a task graph with a large number of logic-nodes, the runtime of placement and routing would increase rapidly. In order to decrease the runtime, a complex task graph is required to be partitioned into several subgraphs. The details about partition approach can be found in Le Beux et al.²⁷ For a practical application, trade-off between runtime and performance is required in the development of configurations for Embryonics.

Conclusions and future work

This article presents an approach to implement the development of configurations for Embryonics based on graphic mapping. Based on metric embedding technology, the problem of configurations is formulated to BQAP, which can be viewed as a placement and routing problem with constraint of Embryonics architecture. A genetic algorithm with staged research is used to find a placement matrix. Also, an IACA provides a valid routing matrix based on the placement matrix. After this, an optimized configuration for LUT-based Embryonics can be found. A $4 \times 4$ multiplier has shown the effectiveness of the proposed approach. Using the proposed approach, a designer can accomplish a design of Embryonics quickly. Furthermore, our approach is also suitable for off-line self-repair of Embryonics. In extensions to this work, we plan to look into using this approach for dynamic reconfiguration of Embryonics.

Footnotes

Academic Editor: Xiaotun Qiu

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This work was supported by the National Natural Science Foundation of China (grant no. 51275520).

References

Yang

Jung

Cho

. Self-repairing digital system with unified recovery process inspired by endocrine cellular communication. IEEE T VLSI Syst 2013; 21: 1027–1040.

Tempesti

Mange

Mudry

. Self-replicating hardware for reliability: the Embryonics project. ACM J Emerg Technol 2007; 3: 9.

Mange

Sipper

Stauffer

. Toward self-repairing and self-replicating hardware: the Embryonics approach. In: Proceedings of the second NASA/DoD workshop on evolvable hardware, Palo Alto, CA, 13–15 July 2000, pp.205–214. New York: IEEE.

Ortega-Sanchez

Torres-Jimenez

Morales-Cruz

. Routing of embryonic arrays using genetic algorithms. In: Tyrrell

Haddow

Torresen

(eds) Evolvable systems: from biology to hardware. New York: Springer, 2003, pp.249–261.

Lala

Kumar

Parkerson

. On self-healing digital system design. Microelectr J 2006; 37: 353–362.

Lala

Kumar

. An architecture for self-healing digital systems. J Electron Test 2003; 19: 523–535.

Matoušek

. Lectures on discrete geometry. Vol. 108. New York: Springer, 2002.

Betz

Rose

. Vpr: a new packing, placement and routing tool for FPGA research. In: Luk

Cheung

PYK

Glesner

(eds) Field-programmable logic and applications. New York: Springer, 2004, pp.213–222.

Gréwal

Areibi

. Starplace: a new analytic method for FPGA placement. INTEGRATION 2011; 44: 192–204.

10.

Gort

Anderson

. Analytical placement for heterogeneous FPGAs. In: 22nd international conference on field programmable logic and applications (FPL), Oslo, 29–31 August 2012, pp.143–150. New York: IEEE.

11.

Gopalakrishnan

Pileggi

. Architecture-aware FPGA placement using metric embedding. In: Proceedings of the 43rd annual design automation conference, San Francisco, CA, 24–28 July 2006, pp.460–465. New York: ACM.

12.

Jang

Pan

. A3MAP: architecture-aware analytic mapping for networks-on-chip. ACM T Des Automat El 2012; 17: 26.

13.

Nair

. A simple yet effective technique for global wiring. IEEE T Comput Aid D 1987; 6: 165–172.

14.

Hill

. A CAD system for the design of field programmable gate arrays. In: Proceedings of the 28th ACM/IEEE design automation conference, 21 June 1991, pp.187–192. New York: ACM.

15.

Brown

Rose

Vranesic

. A detailed router for field-programmable gate arrays. IEEE T Comput Aid D 1992; 11: 620–628.

16.

Ebeling

McMurchie

Hauck

. Placement and routing tools for the triptych FPGA. IEEE T VLSI Syst 1995; 3: 473–482.

17.

Seffrin

Biedermann

. Cellular-array implementations of bio-inspired self-healing systems: state of the art and future perspectives. In: Biedermann

Molter

(eds) Design methodologies for secure embedded systems. New York: Springer, 2011; pp.151–170.

18.

Harel

Koren

. Graph drawing by high-dimensional embedding. In: Goodrich

Kobourov

(eds) Graph drawing. New York: Springer, 2002, pp.207–219.

19.

Sahni

Gonzalez

. P-complete approximation problems. J ACM 1976; 23: 555–565.

20.

Drezner

. A new genetic algorithm for the quadratic assignment problem. INFORMS: J Comput 2003; 15: 320–330.

21.

Shin

Kim

. Power-aware communication optimization for networks-on-chips with voltage scalable links. In: Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, Stockholm, 8–10 September 2004, pp.170–175. New York: ACM.

22.

Dorigo

Birattari

Stutzle

. Ant colony optimization. IEEE Comput Intell M 2006; 1: 28–39.

23.

Maniezzo

Gambardella

De Luigi

. Ant colony optimization. In: Onwubolu

Babu

(eds) New optimization techniques in engineering. New York: Springer, 2004, pp.101–121.

24.

Samie

Dragffy

Pipe

. UNITRONICS: a novel bio-inspired fault tolerant cellular system. In: NASA/ESA conference on adaptive hardware and systems (AHS), San Diego, CA, 6–9 June 2011, pp.58–65. New York: IEEE.

25.