عنوان مقاله
مدل هزینه و سرعت برای مسیریاب های سوراخ کرم k-ary n-cube
فهرست مطالب
مقدمه
پیشینه
توابع و وظایف پایه مسیریاب
مدل هزینه پارامتری
کاربردها
نتیجه گیری
بخشی از مقاله
مسیریابی تطبیقی
مسیریابی تطبیقی امکان انتخاب پویای مسیرها براساس اطلاعات مربوط به کانال های موجود را فراهم آورده و بدین طریق با استفاده بهتر از منابع شبکه تاخیر شبکه را کاهش و پهنای باند شبکه را افزایش می دهد. اما اگرچه مسیریابی تطبیقی ، آزادی مسیریابی را افزایش می دهد، اما هزینه پیشگیری از بن بست را نیز افزایش می دهد. در این راستا به سخت افزارهای اضافی مهمی نیاز می باشد. به علاوه، مسیریابی تطبیقی، پیچیدگی منطق تصمیم مسیریابی و اندازه کراس بار را افزایش می دهد
کلمات کلیدی:
A Cost and Speed Model for k-ary n-Cube Wormhole Routers Andrew A. Chien, Member, IEEE Abstract—The evaluation of advanced routing features must be based on both of costs and benefits. To date, adaptive routers have generally been evaluated on the basis of the achieved network throughput (channel utilization), ignoring the effects of implementation complexity. In this paper, we describe a parameterized cost model for router performance, characterized by two numbers: router delay and flow control time. Grounding the cost model in a 0.8 micron gate array technology, we use it to compare a number of proposed routing algorithms. From these design studies, several insights into the implementation complexity of adaptive routers are clear. First, header update and selection is expensive in adaptive routers, suggesting that absolute addressing should be reconsidered. Second, virtual channels are expensive in terms of latency and cycle time, so decisions to include them to support adaptivity or even virtual lanes should not be taken lightly. Third, requirements of larger crossbars and more complex arbitration cause some increase in the complexity of adaptive routers, but the rate of increase is small. Last, the complexity of adaptive routers significantly increases their setup delay and flow control cycle times, implying that claims of performance advantages in channel utilization and low load latency must be carefully balanced against losses in achievable implementation speed. Index Terms—Routing networks, multicomputers, gate array, wormhole routing, adaptive routing, parallel computing, deadlock prevention. —————————— ✦ —————————— 1 INTRODUCTION OUTING networks are critical to the performance of parallel machines because they determine the efficiency with which processing elements can communicate and cooperate. Three fundamental characteristics of a network are its topology, routing, and flow control policies. Though a wide variety of network design have been studied and implemented, we focus on a subset in order to make an implementation study feasible. We consider a family of networks which have k-ary n-cube topologies, allow adaptive or multipath routing (i.e., choose paths dynamically based on router status), and implement wormhole routing, because deterministic versions of these networks have been used in a number of parallel machines. We focus on examining the increased implementation complexity due to adaptive routing with a particular emphasis on how these changes affect achievable router speed. Our evaluation focuses on two metrics of router implementation speed: setup delay and flow control cycle time. These two metrics directly affect two critical dimensions of router performance: latency and bandwidth. Many studies have been published reporting router performance in network clock cycles, assuming unit router delay (or some other arbitrary number of cycles). But, because the network clock cycles for different routers are generally not the same, results from these studies cannot be compared directly. In this paper, we develop a parametric cost and speed model for a family of routers based on a canonical architecture. This model allows us to evaluate and compare the cost of various routing features in hardware resources as well as achievable router speed. Making concrete comparisons requires a concrete cost and speed model. We instantiate our parametric model, using a 0.8 micron gate array technology, and produce specific constants for all aspects of the model. This model is then used to compare a selection of routing algorithms: dimension order [14], planar adaptive [8], turn model [29], and *-channels [6]. The comparison produces a variety of insights about the relative latency and achievable clock rate of these routers. In particular, we find that all of the adaptive routers we consider are significantly slower (longer setup latency and lower clock speeds) than deterministic routers due to header selection cost and the requirement of virtual channels for deadlock prevention. The negative performance impact of virtual channels is particularly severe, incurring setup latency and reducing network clock speeds. Consequently, a designer of routing networks must carefully balance the benefits of adaptive routing against these significant costs in deciding whether or not to include adaptivity.
