A new routing algorithm is proposed for FPGA to improve the increasing transformation cost of pseudo-Boolean Satisfiability algorithm in the routing process, which combined advantages of pseudo-Boolean Satisfiability ...
详细信息
ISBN:
(纸本)9783037853849
A new routing algorithm is proposed for FPGA to improve the increasing transformation cost of pseudo-Boolean Satisfiability algorithm in the routing process, which combined advantages of pseudo-Boolean Satisfiability and geometric routing algorithm. In the routing process, one of geometric routing algorithm-VPR5.0 was chosen firstly for FPGA routing. If not successful, then use pseudo-Boolean Satisfiability algorithm. Technique of static symmetry-breaking is also adding to carry out pretreatment of pseudo-Boolean constraints, detecting and breaking the symmetries in the routing flow. The purpose was to prune search path, and the cost was consequently reduced. Preliminary experiments results show that the hybrid approach can reduce the runtime observably, speed up the solving process, and have no adverse affect on overall program.
Directional antenna provides tremendous performance improvement in an ad hoc network. There are many applications such as multimedia and real time, which requires guaranteed QoS (quality of service) in the network. In...
详细信息
ISBN:
(纸本)9781467359986
Directional antenna provides tremendous performance improvement in an ad hoc network. There are many applications such as multimedia and real time, which requires guaranteed QoS (quality of service) in the network. In this paper, we present QoS routing algorithm which finds a optimal path from source to destination as well as for other nodes in the network. Route discovery is initiated by source node and routing path is selected based on routing metric value which is having delay and bandwidth as constraints. The probability updation rule is used to increase the probability of beam in the direction of successful transmission and it reduces the routing overhead in retransmission. The simulation results demonstrate the routing overhead which reduces as the number of iteration increases. It shows significant improvement in terms of average routing overhead with directional transmission over omnidirectional transmission.
In this paper we have presented a new fault-tolerant Irregular Modified Alpha Multi-stage Interconnection Network (MALN-2). MALN-2 is a double switch fault-tolerant interconnection network with more alternate paths wi...
详细信息
ISBN:
(纸本)9783642321115
In this paper we have presented a new fault-tolerant Irregular Modified Alpha Multi-stage Interconnection Network (MALN-2). MALN-2 is a double switch fault-tolerant interconnection network with more alternate paths with full accessibility. It is better than existing Modified Alpha Network. The paper also presents the fault-tolerant routing Algorithm for the proposed irregular Interconnection Network.
We propose a primary traffic based multihop routing with the cooperative transmission (PTBMR-CT) algorithm that enlarges the hop transmission distances to reduce the number of cognitive receivers on the route from the...
详细信息
ISBN:
(纸本)9781457720710
We propose a primary traffic based multihop routing with the cooperative transmission (PTBMR-CT) algorithm that enlarges the hop transmission distances to reduce the number of cognitive receivers on the route from the cognitive source (CS) to the cognitive destination (CD). In each hop, from the cognitive nodes in a specified area depending on the status of the primary traffic, the cognitive node that is farthest away from the cognitive sender is selected as the cognitive receiver. However, when the primary source (PS) is transmitting the data to the primary destination (PD), another cognitive node is also selected to be the cognitive receiver for the cooperative transmission from the cognitive nodes that are in a specified area. The cooperative transmission is performed if the PS still transmits the data to the PD when the cognitive receiver of the next hop is being searched. The simulation results show that the average number of cognitive receivers is reduced by the PTBMR-CT compared to the conventional primary traffic based farthest neighbor routing (PTBFNR), and the conventional PTBFNR is outperformed by the PTBMR-CT in terms of the average end-to-end reliability, the average end-to-end throughput, and the average required transmission power of transmitting the data from the CS to the CD.
Context aware routing (CAR) is a hybrid routing algorithm for opportunistic networks, which uses destination-sequence distance-vector (DSDV) algorithm and probabilistic routing in connected regions and between the con...
详细信息
ISBN:
(纸本)9781467318556;9781467318570
Context aware routing (CAR) is a hybrid routing algorithm for opportunistic networks, which uses destination-sequence distance-vector (DSDV) algorithm and probabilistic routing in connected regions and between the connected regions, respectively. We find that the control overhead of CAR is relatively high due to the utilization of DSDV and the default time-to-live (TTL) value of data affects the delivery rate. To solve these problems, we proposed an effective and reliable hybrid routing algorithm (ERHR). In ERHR, the optimized link-state routing version 2 (OLSRv2) is used in connected regions to reduce the control overhead, and the modification of TTL value makes a progress on the aspect of the data delivery rate. Theoretical analysis and simulation results show that the proposed algorithm has a better performance in terms of control overhead, data delivery rate and data retransmission overhead.
This paper considers the problem of power-efficient distributed estimation of vector parameters related to localized phenomena so that both the subset of sensor selection and the routing structure in a wireless sensor...
详细信息
ISBN:
(纸本)9780769547077
This paper considers the problem of power-efficient distributed estimation of vector parameters related to localized phenomena so that both the subset of sensor selection and the routing structure in a wireless sensor network are optimized jointly in order to obtain the best possible estimation performance at a given querying node, for a given total power budget. We first formulate our problem as an optimization problem and show that it is NP-Hard. Then, we design two algorithms: a fixed-tree relaxation-based and a novel and very efficient local distributed optimization to optimize jointly the sensor selection and the routing structure. We also provide a lower bound for our optimization problem and show that our local distributed optimization algorithm provides a performance that is close to this bound. Although there is no guarantee that the gap between this lower bound and the optimal solution of the main problem is always small, our numerical experiments support that this gap is actually very small in many cases. An important result from our work is that because of the interplay between the communication cost over the links and the gains in estimation accuracy obtained by choosing certain sensors, the traditional shortest-path-tree routing structure, widely used in practice, is no longer optimal, that is, our routing structures provide a better trade-off between the overall power efficiency and the final estimation accuracy obtained at the querying node. Comparing to more conventional sensor selection and fixed routing algorithms, our proposed joint sensor selection and routing algorithms yield a significant amount of energy saving.
In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm...
详细信息
ISBN:
(纸本)9780769547077
In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under light constraints on the edge lengths and induces a total exchange of at most 6n node identifiers. Its total computational complexity is O(n Delta), with Delta the maximum degree of the communication graph. The second algorithm that we present is a simple and efficient algorithm to route messages in this planar graph that requires routing tables with only three entries. We support these theoretical results by simulations showing the robustness of our algorithms when the coordinates are inaccurate.
Continuous technology scaling has made aging mechanisms such as Negative Bias Temperature Instability (NBTI) and electromigration primary concerns in Network-on-Chip (NoC) designs. In this paper, we model the effects ...
详细信息
ISBN:
(纸本)9781450311991
Continuous technology scaling has made aging mechanisms such as Negative Bias Temperature Instability (NBTI) and electromigration primary concerns in Network-on-Chip (NoC) designs. In this paper, we model the effects of these aging mechanisms on NoC components such as routers and links using a novel reliability metric called Traffic Threshold per Epoch (TTpE). We observe a critical need of a robust aging-aware routing algorithm that not only reduces power-performance overheads caused due to aging degradation but also minimizes the stress experienced by heavily utilized routers and links. To solve this problem, we propose an aging-aware adaptive routing algorithm and a router microarchitecture that routes the packets along the paths which are both least congested and experience minimum aging stress. After an extensive experimental analysis using real workloads, we observe a 13%, 12.7% average overhead reduction in network latency and Energy-Delay-Product-Per-Flit (EDPPF) and a 10.4% improvement in performance using our aging-aware routing algorithm.
Network-on-Chip (NoC) architectures have emerged as a better replacement of the traditional bus-based communication in the many-core era. However, continuous technology scaling has made aging mechanisms such as Negati...
详细信息
ISBN:
(纸本)9783981080186
Network-on-Chip (NoC) architectures have emerged as a better replacement of the traditional bus-based communication in the many-core era. However, continuous technology scaling has made aging mechanisms such as Negative Bias Temperature Instability (NBTI) and electromigration primary concerns in NoC design. In this paper 1, we propose a novel system-level aging model to model the effects of asymmetric aging in NoCs. We observe a critical need of a holistic aging analysis, which when combined with power-performance optimization, poses a multi-objective design challenge. To solve this problem, we propose a Mixed Integer Linear Programming (MILP)based aging-aware routing algorithm that optimizes the various design constraints using a multi-objective formulation. After an extensive experimental analysis using real workloads, we observe a 62.7%, 46% average overhead reduction in network latency and Energy-Delay-Product-Per-Flit (EDPPF) and a 41% improvement in Instructions Per Cycle (IPC) using our aging-aware routing algorithm.
This paper proposes a novel, adaptive routing scheme for Network-on-Chip (NoC). In particular, the proposed routing scheme decides on the output port of an incoming flit by taking into account the dynamic traffic and ...
详细信息
ISBN:
(纸本)9781467351652;9780769549149
This paper proposes a novel, adaptive routing scheme for Network-on-Chip (NoC). In particular, the proposed routing scheme decides on the output port of an incoming flit by taking into account the dynamic traffic and power consumption on neighboring router links. For that, a simple, generic, and efficient nonlinear control law is built, based on fuzzy logic control, to dynamically calculate the input links cost. Although we focus on bufferless NoCs, it can also be applied to buffered NoCs as well. The additional digital logic required for the proposed scheme is not in the router critical path, and, therefore, imposes no additional latency. We demonstrate, via simulative evaluation of light to heavy congestion conditions, that the proposed scheme outperforms representative conventional counterparts in terms of throughput and latency. Thus, the effectiveness of the proposed scheme is shown, as the performance is consistently better.
暂无评论