Abstract
Whereas the established interconnection networks (ICTN) achieve low latency by operating in the linear region, i.e. oversizing the fabric, the recent strict cost and power constrains demand more efficient utilization of future networks. Increasing the utilization of lossless ICTNs may, however, lead to saturation and performance degradation owing to HOL-blocking. The current solution to HOL-blocking consists of using Virtual Output Queueing (VOQ), whose quadratical scalability is expensive in large networks. To improve VOQ’s scalability we have proposed the Destination-Based Buffer Management (DBBM), a scheme that compares well with VOQ. Whereas previously we have analyzed DBBM’s basic operation and performance, in this paper we have set two different goals. First we focus on how the different DBBM mappings can impact the cost/performance of multistage ICTNs. Next, because DBBM can introduce unfairness, this constitutes the second theme of our paper. The new results show that DBBM with modulo-4/8 mapping performs very well for only a fraction of the VOQ cost. Also in terms of fairness DBBM shows promise, because it (i) keeps the unfairness degree independent of both topology and routing, while (ii) minimizing the number of flows affected by unfairness.
This work was supported by CICYT under Grant TIC2003-08154-C06.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barcelona Supercomputing Center (BSC) (November 2004), http://www.bsc.org.es
Dally, W.J.: Virtual-channel Flow Control. In: Proceedings of the 17th Int. Symp. on Computer Architecture. ACM SIGARCH, May 1990, vol. 18(2), pp. 60–68 (1990)
Dally, W.J., Towles, B.: Principles and Practices of Interconnection Networks, San Francisco, CA. Morgan Kaufmann, San Francisco (2004)
Duato, J., Flich, J., Nachiondo, T.: Cost-Effective Technique to Reduce HOL-blocking in Single-Stage and Multistage Switch Fabrics. In: Euromicro Conference on Parallel, Distributed and Network-based Processing, February 2004, pp. 48–53 (2004)
Duato, J., Johnson, I., Flich, J., Naven, F., García, P., Nachiondo, T.: A New Scalable and Cost-Effective Congestion Management Strategy for Lossless Multistage Interconnection Networks. In: Int. Symp. on High-Performance Computer Architecture (February 2005)
Earth Simulator Center, http://www.es.jamstec.go.jp/esc/eng/index.html
IBM BG/L Team, An Overview of BlueGene/L Supercomputer. In: ACM Supercomputing Conference, 2002.
InfiniBand Trade Association, InfiniBand Architecture. Specification Volume 1. Release 1.0. Available at http://www.infinibandta.com/
Jurczyk, M., Schwederski, T.: Phenomenon of Higher Order Head-of-Line Blocking in Multistage Interconnection Networks under Nonuniform Traffic Patterns. IEICE Transactions on Information and Systems, Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing E79-D(8), 1124–1129 (1996)
Minkenberg, C.: On Packet Switch Design, Ph.D. Thesis, Eindhoven University of Technology (September 2001)
Myrinet, 2000 Series Networking, (2000), Available at http://www.cspi.com/multicomputer/products/2000seriesnetworking/2000networking.htm
Nachiondo, T., Flich, J., Duato, J.: Efficient Reduction of HOL blocking in Multistage Networks. In: Workshop on Communication Architecture for Clusters (CAC 2005) (April 2005)
Pfister, G.F., Norton, V.A.: Hot Spot Contention and Combining in Multistage Interconnection Networks. IEEE Transactions on Computers C-34(10), 943–948 (1985)
Quadrics QsNet, Available at http://doc.quadrics.com
Shang, L., Peh, L.S., Jha, N.K.: Dynamic Voltage Scaling with Links for Power Optimization of Interconnection Networks. In: Proc. Int. Symp. on High-Performance Computer Architecture, February 2003, pp. 91–102 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nachiondo, T., Flich, J., Duato, J., Gusat, M. (2005). Cost / Performance Trade-Offs and Fairness Evaluation of Queue Mapping Policies. In: Cunha, J.C., Medeiros, P.D. (eds) Euro-Par 2005 Parallel Processing. Euro-Par 2005. Lecture Notes in Computer Science, vol 3648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549468_112
Download citation
DOI: https://doi.org/10.1007/11549468_112
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28700-1
Online ISBN: 978-3-540-31925-2
eBook Packages: Computer ScienceComputer Science (R0)