# Design and Implementation of Nanotechnology QCA Geometric Greedy Router

Authors: Lamjed Touil; Ismail Gassoumi; Abdellatif Mtibaa
Journal: Journal of Electrical and Computer Engineering
 (2021)

---

## Abstract

This paper presents an optimized geometric greedy router (GGR) based on quantum dot cellular automata (QCA) technology. The proposed structure of GGR is based on a spanning tree of the network. This type of communication does not require an IP address. It uses only local information and can be used in many communication devices. In this paper, we first describe the principal components of the router and then we present their QCA architecture. The QCA technology is the most likely alternative to replace conventional circuits (CMOS) due to their very low power consumption and high processing speed. To consider integration with other complex circuit, we have utilized QCA clock-phase-based technique for the proposed design architecture. The results obtained using the QCA designer tool exhibit the superiority of the presented architecture over the existing designs. The proposed structure shows a reduction of 30% reduction in occupied space. The power dissipation rate of the proposed design is analyzed by QCAPro tool to approve its reliability.


---

## Body

## 1. Introduction

The complementary metal oxide semiconductor (CMOS) technology has many defects, such as short channel effect and high power consumption; it cannot, therefore, continue to follow Morrie’s law by increasing the number of devices per chip [1]. It creates the need for nanoscale devices, with high-performance rates and low power consumption. These recent nanoscale devices have the potential to enable progressions in different domains such as industrial, biomedical, and military fields. For these types of applications, classical communication networks, such as IP routing, are not suitable. In fact, these types of applications are very greedy for size, energy, and memory consumption [2]. The design of a geometric greedy router using the quantum dot cellular automata (QCA) can present an alternative to resolve these problems.The quantum dot cellular automata (QCA) technology is one of the important emerging nanotechnologies that have attracted much researcher’s attention in recent years. Such advantages led researchers to develop several projects detailing the construction of QCA circuits. In the recent years, several circuits such as address [3, 4], sequential circuits [2, 5], switching circuits [6, 7], reversible logic circuit [8, 9], and memories [10, 11] have been designed. On the contrary, to cope with the challenge of IOT, big data domains and the need to achieve data rates of up to multiple gigabits per second require the use of more efficient routing algorithms to avoid network bottlenecks. In the greedy routing method, the main aim is to achieve another routing process by having each participant store only a partial knowledge based on the network.In the recent years, different studies of geometric greedy router have been proposed [12].This routing method requires very efficient electronic support. In this paper, we present an optimized architecture of geometric greedy router based on QCA technology.The paper is organized as follows. Section2 presents the basic concept of QCA. Section 3 explains briefly the technique of the tree-based greedy routing. Section 4 covers the proposed architectures of the QCA geometric greedy router. Section 4 presents the simulation results of the proposed work along with discussion. Power dissipation analysis is carried out in Section 5. We conclude the paper with Section 6.


## 2. Preface to Quantum Dot Cellular Automata

The basic QCA cell is illustrated in Figure1. The QCA cell can be considered as a square including four quantum dots which are occupied by a pair of electrons. The cell comprises four quantum dots and two mobile electrons which are able to confine electric charges. These electrons tend to locate themselves and arranged diagonally in the cell. The repulsive force between two electrons pushes them as far as possible. There are two polarization states, which present logic “0” and “1,” as shown in Figure 1 [13].Figure 1
Schematics of the basic QCA cells.In QCA technology, the polarization of adjacent cells is performed by coulomb interaction, as shown in Figure2(b). Polarization (P) is defined as the following expression:(1)Polarizationp=P1+P3−P2+P4P1−P2+P3+P4.Figure 2
Propagation of binary information.The polarization of the electrons in the quantum dots are presented asP1, P2, P3, and P4 (Figure 2(a)). Equation (1) presents the value of polarization of QCA cell. If an electron is present, Pi = 1, otherwise it is equal 0.Inverter and majority gates are the essential logic element in the QCA circuits which are realized by some QCA cells, as shown in Figure3 [13]. The majority gate can be used to generate an “AND” or an “OR” logic, by putting one of the inputs as “0” and “1,” respectively.Figure 3
Realization of logical OR and AND gates.The QCA clocking system synchronization is used for controlling the potential barriers between the adjacent quantum dots. The QCA clocking system consists of four phases, as illustrated in Figure4. The phases are switch, hold, release, and relax [14]. The barriers are raised during the switch phase, and a cell is influenced by the polarization of its adjacent cells. The barriers are high in the hold phase, and the polarization of the cell is retained. During the release phase, the barriers are lowered, and the cell loses the polarity. During the relaxing phase, the cell is nonpolarized.Figure 4
QCA clock phases.In QCA, there are two different forms of crossover: coplanar and multilayer crossovers (Figure5(a) and 5(b)). While multilayer crossover requires at least three layers for implementation, coplanar crossover uses only one layer. Multilayer QCA circuits consume much less area as compared to coplanar circuits.Figure 5
Signal crossover schemes: (a) coplanar crossing; (b) multilayer crossing.
(a)(b)


## 3. Greedy Router

In geometric routing, a rather simple stateless distributed algorithm routes messages from node to node along a source-destination path, based only on position information (node coordinates). Only local information needs to be stored in each network node. A greedy routing algorithm forwards every packet to the node in the one-hop neighborhood, which lies closest to the final destination. In GR, virtual coordinates are assigned to each of the nodes of a network. The coordinate distribution is based on other ad hoc network protocols or sensors, such as greedy perimeter stateless routing (GPSR) [15]. In [16], the authors have proposed the use of virtual coordinates in NoGeo routing, the creation of the virtual coordinate assignment protocol (VCAP), and the use of conformal maps to find the coordinates [17]. In GR, a greedy technique is used. As the next hop, the neighbor node with the shortest distance to the destination node is selected.The problem with geometric greedy routing occurs when a packet is in the case that the distance between the current node and the destination is smaller than the distance between its neighbors and the destination. The solution for this problem can be based on the face routing method [18] or using a greedy embedding method [19]. The embedding method can be done using multiple dimensions in Euclidean space [20, 21] or using multiple trees [22, 23] to improve routing performance. In our work, we used the method proposed in [24]. This method starts with the creation of a spanning tree and the adoption of a set of coordinates to each node of the network. Figure 6 presents this step. It consist of(i)
The creation of spanning tree (Figure6(a))(ii)
Assignation of a number (from 1 to n) for the children of each node (Figure6(b))(iii)
Give numbers to the children of each node (from 1 to n)(iv)
Assign (0, ..., 0) to the root node(v)
A number previously is given to each child, replacing the first zero of their coordinates (Figure6(c))Figure 6
(a) Network topology. (b) Spanning tree and children numbering. (c) Coordinate set of each node given.The tree depth presents the number of coordinates will be attributed to the nodes. The number of bits allocated to represent the coordinates in the router implementation is proportional to the number of children of the node. During the process, several steps must be established. When the router structure is created, the embedding tree has already been established and each generated node is aware of the coordinate set (CS) of its neighbors; the node forward the received packet to the neighbor which has the smallest possible distance to the destination. The processes are repeated until the packet reaches its final destination. Algorithm1 presents the following steps.Algorithm 1: Forwarding a packet to its destination.
(1)
Begin;(2)
whilepacket is not at the destination do(3)
for eachneighbor of present nodedo(4)
find the first pair of different coordinates, comparing bit by bit, between neighbor and destination node; from there, count the number of nonzero coordinates from both CSto encounter distance;(5)
end(6)
compare found distances;(7)
forward packet to node with smallest distance to destination;(8)
endThe distance between nodes is computed according to the number of hops that must travel in the tree through the nodes, taking into consideration the common ancestors of neighbor nodes and the number of nonzero coordinates in each set.


## 4. Architecture of the QCA Geometric Greedy Router

Figure7 shows the block diagram of the geometric greedy router.Figure 7
Geometric greedy router [25].Two tasks must be accomplished in the distance calculator module. The first task is based on the distance calculator algorithm (Algorithm1). The model of the first part of the distance calculator is depicted in Figure 8. The second task is reserved for the destination node and the distance comparator determination.Figure 8
Circuit diagram of the distance calculator.The architecture of the greedy router is composed of several logic gates such as OR, XOR, NAND, and multiplexer. The optimized QCA layouts of these logic modules are presented in Figure9.Figure 9
Basic logic gates of distance calculator module: (a) XOR; (b) 2 : 1 Mux; (c) And; (d) Or.
(a)(b)(c)(d)A proposed realization of circuit diagram of distance calculator based on QCA technology is presented in Figure10. The proposed architecture is composed by one 2 to 1 QCA multiplexer, two OR gates, two And gates, and one XOR gate.Figure 10
QCA architecture of the distance calculator module (DCM).The next step is to count the number of ‘1’ in the output string that presents the number of marked coordinates. Figure11 shows the architecture of the counter. The circuit, composed by a series-to-parallel converter, is based on eleven Half Adder circuits and two ‘and’ logic gates.Figure 11
Architecture of the counter.The next step is to count the number of ‘1’ in the output string that presents the number of marked coordinates. Figure11 shows the architecture of the counter. The circuit, composed by a series-to-parallel converter, is based on eleven Half Adder circuits and two ‘and’ logic gates.Since the Half adder presents an essential component of the counter, in Figure12(a) and 12(b), we present the optimized QCA layout and result simulation of this component.Figure 12
Half Adder. (a) Layout. (b) Simulation result.
(a)(b)An example of a tree with depth 3 is presented in Figure13. We use a three coordinates to each CS. For tree nodes, we can attribute a maximum number of children of three, so two bits are enough to represent each coordinate.Figure 13
QCA architecture of the countermodule (CM).The comparator circuit presents an essential submodule of the entire system. The comparator compares two binary 3 bits numbers (A, B) and produces three outputs (A > B, A = B, and A < B). The logic circuit of the comparator is presented in Figure14.Figure 14
Comparator circuit.The proposed QCA layout of the comparator circuit is illustrated in Figure15. The assembly of the submodules constitutes the greed router architecture (Figure 16). In the block diagram of the proposed architecture, we used two distance calculators and two counters to receive the coordinates of packet destination and neighbor. After the counters, the results will be used by the comparator. The output will present the destination node for the packet.Figure 15
QCA architecture of the comparator (CMP).Figure 16
Block diagram of the greed router.The QCA architecture of the entire greed router is illustrated in Figure17. The figure presents the inputs and outputs of the system.Figure 17
Block diagram of the greed router.


## 5. Result and Discussion

The comparison between the proposed used logic gates and the existing architectures is given in Tables1–3 . In these tables, the complexity is given by the number of the required cells and the area is given by µm2.Table 1
Comparison results of the used 2-input digital “XOR” gate.
XOR structureCell countSurface (µm2)Crossover[26]600.08Coplanar (rotated cells)[27]290.03Not required[28]280.02Coplanar[29]120.0116Not required[30]130.01Not required[31]100.008Not requiredUsed90.008Not requiredTable 2
Comparative result of 2 : 1 multiplexer.
2:1 muxCell countSurface (µm2)Crossover[32]260.02Coplanar[33]290.02Coplanar[34]280.02Coplanar[35]120.02Coplanar[36]130.01Coplanar[37]120.02WithoutUsed90.0076WithoutTable 3
Comparative result of Half Adder.
Half AdderCell countSurface (µm2)[39]770.08[40]620.08Proposed250.025The proposed QCA distance calculator layout is composed by 96 cells and occupied a surface of 0.313µm2. In [38], the authors have proposed a circuit composed by 154 cells and occupied a surface of 0.461 µm2.Half Adder presents the basic elements of the countermodule. For implementing the half adder in QCA technology, we have used one two-input XOR gate and one two-input AND gate.Figure12 shows the proposed layout of the QCA Half Adder circuit and the simulation result. Table 3 shows a comparison between the proposed Half Adder with the previous works. Half Adder circuit has lower computational complexity and better performances compared to existing ones.The countercircuit is composed by ten Half Adder circuits and two AND logic gates. It occupies a surface of 1.73µm2. The proposed circuits are simulated using QCADesigner tool version 2.0.3 [40]. This allows users to do a custom layout and also verify QCA design by simulation. A nominal cell size of 18 nm by 18 nm is assumed. The propagation delays from cell to cell required a maximum cell count in a clock zone.The minimum separation between two different signal wires is width of two cells. We have used multilayer crossovers for wire crossings essentially depending on the complexity of the circuit. The essential QCA parameters are presented in Table4.Table 4
Simulation parameters.
ParameterValueCell size18 nm∗18 nmDot5 nmCell separation2 nmSimulation engineBistable approximation/coherence vectorRadius of effect65 nmNumber of samples12800Convergence tolerance0.001000Temperature1.000000Relative permittivity12.900000Clock high9.800000e−022Clock low3.800000e−023Clock shiftcty0.000000Clock amplitude factor layer2.000000Separation11.500000Maximum iterations per sample100Relaxation time1.000000e−015


## 6. Conclusion

In this paper, an optimized design of nanotechnology geometric greedy router architecture in the QCA technology was proposed. The GGR presents the principal components of the router, and this work presents an essential step in the building of QCA circuits for low power in digital nanocommunications systems. Our main focus is to propose a prototype of a very low-power GGR module optimized in terms of cell count and area. Results of simulation are shown by QCADesigner version 2.0.3. An interesting future work could be to develop several applications based on this GGR module.



---

*Source: 3935091-2021-09-15.xml*