Temperature-aware task scheduling algorithm for soft real-time multi-core systems

High temperature will affect the stability and performance of multi-core processors. A temperature-aware scheduling algorithm for soft real-time multi-core systems is proposed in this paper, namely LTCEDF (Low Thermal Contribution Early Deadline First). According to the core temperature and thread thermal contribution, LTCEDF performs thread migration and exchange to avoid thermal saturation and to keep temperature equilibrium among all the cores. The core temperature calculation method and the thread thermal contribution prediction method are presented. LTCEDF is simulated on ATMI simulator platform. Simulation results show that LTCEDF can not only minimize the thermal penalty, but also meet real-time guarantee. Moreover, it can create a more uniform power density map than other thermal-aware algorithms, and significantly reduce thread migration frequency.     

Power Supply Noise Aware Task Scheduling on Homogeneous 3D MPSoCs Considering the Thermal Constraint

Thanks to the emerging 3D integration technology, The multiprocessor system on chips (MPSoCs) can now integrate more IP cores on chip with improved energy efficiency. However, several severe challenges also rise up for 3D ICs due to the die-stacking architecture. Among them, power supply noise becomes a big concern. In the paper, we investigate power supply noise (PSN) interactions among different cores and tiers and show that PSN variations largely depend on task assignments. On the other hand, high integration density incurs a severe thermal issue on 3D ICs. In the paper, we propose a novel task scheduling framework considering both the PSN and the thermal issue. It mainly consists of three parts. First, we extract current stimuli of running tasks by analyzing their power traces derived from architecture level simulations. Second, we develop an efficient power delivery network (PDN) solver to evaluate PSN magnitudes efficiently. Third, we propose a heuristic algorithm to solve the formulated task scheduling problem. Compared with the state-of-the-art task assignment algorithm, the proposed method can reduce PSN by 12% on a 2 × 2 × 2 3D MPSoCs and by 14% on a 3 × 3 × 3 3D MPSoCs. The end-to-end task execution time also improves as much as 5.5% and 7.8% respectively due to the suppressed PSN.     

Thermal management in 3d networks-on-chip using dynamic link sharing

3D integration is a practical solution for overcoming the problems of long and slow global wires in current and future generations of integrated circuits. This emerging technology stacks several die slices on top of each other in a single chip. It provides higher-bandwidth and lower-latency in the third dimension than a 2D design due to extremely shorter inter-layer distances. However, thermal challenges are a key impediment to stacking logic dies on top of each other. Particularly, routers in a 3D network-on-chip (NoC) are a main source of thermal hotspots, limiting the potential performance gains of the 3D integration. In this paper, we take advantage of the low-latency 3D vertical links to design a temperature-aware router architecture for 3D NoCs. This architecture reduces the peak temperature of routers, particularly routers that are farther from the heat sink, by balancing the traffic across all layers in a temperature-aware distributed way. This way, a router with high temperature can borrow the link and crossbar bandwidth of the routers in the layers closer to the heat sink to forward its packets, effectively offloading part of its traffic to them to reduce its temperature.Experimental results show that the proposed method can control the temperature of 3D NoCs and reduce the temperature gradient across the network with minimized negative impact on performance, compared to a state-of-the-art 3D NoC temperature management method.     

Application Specific Routing Algorithms for Networks on Chip

In this paper we present a methodology to develop efficient and deadlock free routing algorithms for Network-on-Chip (NoC) platforms which are specialized for an application or a set of concurrent applications. The proposed methodology, called Application Specific Routing Algorithm (APSRA), exploits the application specific information regarding pairs of cores which communicate and other pairs which never communicate in the NoC platform to maximize communication adaptivity and performance. The methodology also exploits the known information regarding concurrency/non-concurrency of communication transactions among cores for the same purpose. We demonstrate, through analysis of adaptivity as well as simulation based evaluation of latency and throughput, that algorithms produced by the proposed methodology give significantly higher performance as compared to other deadlock free algorithms for both homogeneous as well as heterogeneous 2D mesh topology NoC systems. For example, for homogeneous mesh NoC, APSRA results in approximately 30% less average delay as compared to Odd-Even algorithm just below saturation load. Similarly the saturation load point for APSRA is significantly higher as compared to other adaptive routing algorithms for both homogeneous and non-homogeneous mesh networks.     

Adaptive inter-layer message routing in 3D networks-on-chip

Existing routing algorithms for 3D deal with regular mesh/torus 3D topologies. Today 3D NoCs are quite irregular, especially those with heterogeneous layers. In this paper, we present a routing algorithm targeting 3D networks-on-chip (NoCs) with incomplete sets of vertical links between adjacent layers. The routing algorithm tolerates multiple link and node failures, in the case of absence of NoC partitioning. In addition, it deals with congestion. The routing algorithm for 3D NoCs preserves the deadlock-free propriety of the chosen 2D routing algorithms. It is also scalable and supports a local reconfiguration that complements the reconfiguration of the 2D routing algorithms in case of failures of nodes or links. The algorithm incurs a small overhead in terms of exchanged messages for reconfiguration and does not introduce significant additional complexity in the routers. Theoretical analysis of the 3D routing algorithm is provided and validated by simulations for different traffic loads and failure rates.     

Deadlock-free generic routing algorithms for 3-dimensional Networks-on-Chip with reduced vertical link density topologies

3-Dimensional Networks-on-Chip (3D NoC) have emerged as the promising solution for scalability, power consumption and performance demands of next generation Systems-on-Chip (SoCs) interconnect. Due to the cost in terms of thermal, yield, chip area and design complexity, minimizing the number of Through-Silicon-Via (TSVs) in 3D ICs has become on the most important design issues. In this paper, we will present several stable, simple and deadlock-free generic routing algorithms for 3D NoCs with different reduced vertical link density topologies, which can maintain the 3D NoCs performance and save the system cost (TSV number, chip area, system power, etc.). The experimental results have been extracted from our cycle-accurate GSNOC simulator and have shown that our routing algorithms can maintain the system performance up to reducing 50% of TSVs number in comparison to the 100% TSVs number with ZXY routing algorithm configuration.     

Thermal-Aware Post Layout Voltage-Island Generation for 3D ICs

To reduce the interconnect delay and improve the chip performance, three-dimensional (3D) chip emerged with the rapid increasing of chip integration and chip power density. Therefore, thermal issue is one of the critical challenges in 3D IC design due to the high power density. Multiple Supply Voltages (MSV) technique provides an effcient way to optimize power consumption which in turn may alleviate the hotspots. But the voltage assignment is limited not only by the performance constraints of the design, but also by the physical layout of circuit modules since the modules with the same voltage should be gathered to reduce the power-network routing resource. Especially in 3D designs, the optimization using MSV technique becomes even more complicated since the high temperature also inffuences the power consumption and delay on paths. In this paper, we address the voltage-island generation problem for MSV designs in 3D ICs based on a mixed integer linear programming (MILP) model. First, we propose a general MILP formulation for voltage-island generation to optimize thermal distribution as well as power-network routing resources while maintaining the whole chip performance. With the thermal-power interdependency, an iterative optimization approach is proposed to obtain the convergence. Experimental results show that our thermal-aware voltage-island generation approach can reduce the maximal on-chip temperature by 23.64% with a reasonable runtime and save the power-network routing resources by 16.71%.     

Formal approach to agent-based dynamic reconfiguration in Networks-On-Chip

A Network-On-Chip (NoC) platform is an emerging topology for large-scale applications. It provides a required number of resources for critical and excessive computations. However, the computations may be interrupted by faults occurring at run-time. Hence, reliability of computations as well as efficient resource management at run-time are crucial for such many-core NoC systems. To achieve this, we utilize an agent-based management system where agents are organized in a three-level hierarchy. We propose to incorporate reallocation and reconfiguration procedures into agents hierarchy such that fault-tolerance mechanisms can be executed at run-time. Task reallocation enables local reconfiguration of a core allowing it to be eventually reused in order to restore the original performance of communication and computations. The contributions of this paper are: (i) an algorithm for initial application mapping with spare cores, (ii) a multi-objective algorithm for efficient utilization of spare cores at run-time in order to enhance fault-tolerance while maintaining efficiency of communication and computations at an adequate level, (iii) an algorithm integrating the local reconfiguration procedure and (iv) formal modeling and verification of the dynamic agent-based NoC management architecture incorporating these algorithms within the Event-B framework.     

Enabling fuzzy technologies in high performance networking via an open FPGA-based development platform

Soft computing techniques and particularly fuzzy inference systems are gaining momentum as tools for network traffic modeling, analysis and control. Efficient hardware implementations of these techniques that can achieve real-time operation in high-speed networking equipment as well as other highly time-constrained application fields is however an open problem. We introduce a development platform for fuzzy inference systems with applications to network traffic analysis and control. The platform addresses the current requirements and constraints of high performance networking equipment. For the development process, we set up a methodology and a CAD tool chain that span the entire design process from initial specification in a high-level language to implementation on FPGA devices. An FPGA development board with PCI/PCIe interface is employed to support an open platform that comprises CAD tools as well as IP cores. PCI compatible fuzzy inference modules are implemented as System-on-Programmable-Chip (SoPC). We present satisfactory experimental results from the implementation of fuzzy systems for a number of applications in analysis and control of Internet traffic. These systems are shown to satisfy operational and architectural requirements of current and future high performance routing equipment. The platform proposed allows for the development of prototypes while avoiding large investments and complicated management procedures which constrain the testing and adoption of soft computing techniques in high performance networking.     

WSN中基于混合整数非线性规划的功率分配算法

近期协作路由协议的研究受到广泛关注.然而,现多数协作路由协议是以减少能量消耗为目的,它们并没有考虑在协作路由中的数据包碰撞概率最小化问题.为此,针对无线传感网WSNs(Wireless Sensor Networks)的协作路由,提出基于最小化碰撞概率的功率分配CMPA(Collision Minimization-based Power Allocation)算法.首先,推导了碰撞概率数学模型,并形成了混合整数非线性规划问题.然后,为了降低复杂度,将功率分配和路由选择进行独立处理,同时利用分支界定空间缩小BBSR(Branch-and-Bound Space Reduced)算法求解.仿真结果表明,提出的CMPA算法能够有效地降低碰撞概率和总的传输功率.与OKCR算法相比,CMPA算法的碰撞概率下降了近82%,总的传输功率下降了0.1 dB.     

无虚拟通道的3D NoC ZoneDefense容错路由算法*

3D片上网络能有效解决片上系统的通信问题。本文针对3D Mesh NoC中的节点故障,提出了一种无虚拟通道容错路由算法,称为3D ZoneDefense容错路由算法(3D-ZDFT)。该算法建立在3D防御区域基础之上,3D防御区域能够提供故障体的位置信息。根据防御区域提供的故障体位置信息,3D-ZDFT可提前发现故障位置并改变转发端口,实现容错的同时避免引入死锁。实验结果表明,与HamFA相比,3D-ZDFT有较低的网络延迟和更高的可靠性。面积开销分析显示,3D-ZDFT比HamFA的面积开销高约3.1%。     

Multicast communication in wormhole-routed 2D torus networks with hamiltonian cycle model

In this paper, we propose an efficient multipath multicast routing algorithm in wormhole-routed 2D torus networks. We first introduce a hamiltonian cycle model for exploiting the feature of torus networks. Based on this model, we find a hamiltonian cycle in torus networks. Then, an efficient multipath multicast routing algorithm with hamiltonian cycle model (mulitpath-HCM) is presented. The proposed multipath multicast routing algorithm utilizes communication channels more uniformly in order to reduce the path length of the routing messages, making the multicasting more efficient. Simulation results show that the multicast latency of the proposed multipath-HCM routing algorithm is superior to that of fixed and dual-path routing algorithms.     

Optimizing Decoupling Capacitors in 3D Circuits for Power Grid Integrity

This article studies one of the EDA problems for 3D IC design. The article presents a design automation solution for power grid optimization in 3D ICs. The authors propose a congestion-aware 3D power supply network optimization algorithm, which applies a sequence-of-linear-programs-based method to optimize the power grid design. We explore the trade-offs between MIM decaps and traditional CMOS decaps in chip design, and we propose a congestion-aware 3D power supply network optimization algorithm to optimize this trade-off. One of the novel features of our work is that it optimizes the power supply network using both conventional CMOS decaps and metal insulator-metal (MIM) decaps. However, because MIM decaps are built between layers of metal interconnects, they present routing blockages to nets that attempt to cross them, and therein lies the trade-off. The properties of MIM decaps make them attractive for both 2D and 3D chips, but we pay particular attention to the 3D decap problem in this article because, first, the power integrity problem is particularly critical in 3D, and requires novel approaches that leverage advances in materials, and second, the added complexity of handling routing blockages in a constrained environment makes the 3D problem especially challenging.     

基于多核微处理器温度感知的线程调度算法

由于多核微处理消耗更多的能量,导致其热点数目增加,温度分布不平衡加剧,因而对性能产生更大的负面影响。为了解决这个问题,提出一种基于多核微处理器温度感知的线程调度算法来减少热紧急事件、提高性能,并在一个Intel的多核微处理器平台上实现了该算法。实验结果表明,在各种负载组合下,该算法可以减少9.6%~78.5%的动态热管理次数。与Linux标准调度算法相比,吞吐率平均可以提高5.2%,最大可提高9.7%。     

适用于多层住宅楼结构的无线智能水表抄表系统

针对通用无线传感器网络（WSN）平台无法满足无线智能水表抄表系统（SWWMRS）低成本、低功耗、高效和高可靠性等方面实际应用需求的问题,设计并实现了一种改进的无线智能水表抄表系统。该系统以适合多层住宅楼结构的抄表应用为目标,结合无线智能水表抄表系统特点、部署环境特征和抄表业务逻辑,提出了一种改进的全网络节点邻接链路发现算法来实现自动组网和集中式的路由管理,在抄表过程中,采用最小化全局转发次数的策略结合最小剩余能量节点避免策略来均衡节点能耗,同时,优化了媒体访问控制（MAC）层防碰撞机制和低功耗空闲监听方案。最后,选取了一栋常规结构的24层居民楼进行测试。实验结果表明：系统在通信距离、功耗、可靠性等方面均能满足实际应用需要,对比通用WSN平台CC2530,系统在通信距离、抄表成功率、效率和功耗方面具有一定的优势。     

3D hexagonal network: modeling, topological properties, addressing scheme, and optimal routing algorithm

The 2D hexagonal mesh, based on triangle plane tessellation, is considered as a multiprocessor interconnection network. The 3D hexagonal mesh is presented as a natural extension of the hexagonal mesh. Although the topological properties of the 2D hexagonal mesh are well known, existing addressing schemes are not suitable to be extended to 3D hexagonal mesh. Then, we present, in this paper, a new addressing scheme and an optimal routing algorithm for 2D hexagonal network based on the distance formula and using shortest paths. We propose also a 3D hexagonal network that can be built with 2D hexagonal meshes as a natural generalization. We also present some topological properties, an efficient addressing scheme, and an optimal routing algorithm based on our 2D routing algorithm.     

Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

对等网中Chord资源查找算法研究

在大规模的对等网络结构中,如何快速准确地确定资源的位置是一个比较突出的问题,基于DHT(DistributedHashTable)资源定位及查找算法是目前比较流行的算法之一,文章介绍了其中具有代表性的Chord算法以及基于Chord的两种改进算法,对其进行了分析比较。     

基于强化学习的温度感知多核任务调度

随着计算机中内核数量的增多,温度感知的多核任务调度算法成为计算机系统中的一个研究热点.近年来,机器学习在各个领域展现出巨大的潜力,彳艮多基于机器学习的系统温度管理研究工作应运而生.其中,强化学习因其较强的自适应性,被广泛地运用于温度感知的任务调度算法中.然而,目前基于强化学习的温度感知任务调度算法系统建模不够准确,很难...     

三维片上网络研究综述

三维片上网络以其更短的全局互连、更高的封装密度、更小的体积等诸多优势,已引起国内外学术界和产业界的高度重视.对三维片上网络的研究,将直接影响一个国家未来三维集成电路和三维芯片产业的发展,也关系到国家安全.近年来,三维片上网络逐渐成为片上网络研究领域的一个重要方向,已取得了许多研究进展,但仍然存在许多挑战性的课题.对三维片上网络的基本问题作了简介;分析了三维片上网络在国内外的研究现状;讨论了三维片上网络研究中的关键问题,归纳出网络拓扑结构、路由机制、性能评估、通信容错、功耗、映射、测试、交换技术、服务质量、流量控制、资源网络接口等12类研究课题;分类综述了关键问题的研究进展;分析了三维片上网络存在的问题;指出,在三维片上网络拓扑结构方面:个性化拓扑结构设计、仿真平台研究开发、基于新型拓扑结构的三维芯片样片试制以及无线技术的引入等,在路由算法方面:适合3D Torus的路由算法、结合无关路由与自适应路由算法优点的新路由算法、适合各种新型拓扑结构的高效路由算法等,在性能评估方面:永久故障的容错、改进仿真程序增加对物理链路的建模、充分考虑通信的局部性等,在功耗方面:对拓扑结构/映射算法/路由算法和布局进行综合优化、动态和静态控制相结合、更为精确的3D NoC功耗模型等,在映射方面:发热均匀性、动态路由策略下映射评估模型的优化、低功耗映射算法、基于优化算法的组合映射等,都将是三维片上网络未来的重要研究课题.