‎"Behind every stack of books there is a flood of knowledge."

The Superior Multiprocessor ARchiTecture (SMART) Interconnects Group


Theoretical Support for Efficient Network Discovery and Reconfiguration Techniques

Project Description of NSF Grant CCR-0209234

A theoretical framework is being developed for the design of efficient network discovery and reconfiguration techniques that result in minimal packet loss, are deadlock-free, and are generally applicable to state-of-the-art interconnection networks used in high performance and highly dependable multiprocessor servers, network-based computing clusters and distributed storage systems. Major research and educational activities include the following: (a) to develop an overall approach and methods on which formal expression of theory can be based, (b) to develop a methodology through which the theoretical framework can be applied in practice, and (c) to develop a simulation platform through which techniques derived from our theoretical framework can be demonstrated and evaluated. Much of this research is being carried out by doctoral students at USC and UCLM. In addition, students in an advanced graduate level course (on the topic of Interconnection Networks) also have the opportunity to participate in the development of the activities mentioned above through a semester-long research project.



USC’s Superior Multiprocessor ARchiTechture (SMART) Group has developed seminal theoretical work in the area of interconnection network deadlock analysis and recovery algorithms. The circumstances and frequency with which deadlocksa phenomenon which results in the ultimate halting of information delivery by a networkoccur are now better understood, and efficient recovery-based algorithms for effectively handling them have been developed through past CCR support. The concepts and ideas born from this research are now serving as the basis for new approaches in such areas as network injection limitation and recovery-oriented routing. They are also cited in the literature and in sections of leading texts including “Interconnection Networks: An Engineering Approach” by Duato, Yalamanchili and Ni, and “Principles and Practices of Interconnection Networks” by Dally and Towles (both books are published by Morgan Kaufmann Publishers).

The current CCR sponsored project extends these theoretical developments to addressing the problem of efficient network discovery and reconfiguration for increased availability, reliability and dependability of networks prone to voluntary or involuntary changes and faults, as conceptually illustrated in the animation above.

We are developing new theory useful for determining the deadlock properties of reconfiguration processes and routing functions for interconnection networks of regular or arbitrary topologies. Since handling deadlocks for routing functions that can change over time is much more complex than for those that remain static, new and more powerful theory is needed that can be applied in both cases. The benefits of such a theory are evidenced by the increasing demand for building adaptive, autonomous, performance-scalable systems that are both highly dependable snd highly available. Several useful methods and new notions have been introduced to simplify the expresssion of the theory without losing generality. Newly defined representations such as CND-tuples and CND relations sufficiently capture both the positions of messages in a network as well as the routing options available to messages at locations within the network. This allows for distributed implementaion of routing functions in forwarding tables across a network to be captured more easily using the method of decomposition and re-constitution. These representations also allow the scope of analysis to be reduced down to critical subclasses on which channel dependency checks should be performed that selectively take into account the destination of messages occupying channels.

The “enabling” ideas born from this research lead to a greater understanding of how to exploit the interaction of dependencies on resources (i.e., network resources) as determined by dynamic functions (i.e., reconfigurable routing algorithms) in order to accomplish certain objectives such as deadlock freedom, uninterrupted service, minimal packet loss, etc. A key idea of the theory is to realize the tracking of only relevant dependency information (as opposed to the entire history of dependencies and changes) using the notion of “filter” constructs. These constructs can be implemented a number of ways but typically specify either positive (allowed) or negative (disallowed) interactions across system resources. Applying this idea in the context of our theory, the runtime state of a changing system can be designed provably to meet certain objectives while imposing a minimum set of restrictions on the use of those resources. Another key idea of the methodology arising from our theory is the notion that reconfiguration processes that provably meet certain objectives can be derived simply from sequences of atomic phases of adding or removing selected resource dependencies.


Through CCR support from 1998 to the present, the SMART Interconnects Group at the USC headed by Timothy Mark Pinkston has developed and made publicly-available user-friendly versions of two network simulators, called FlexSim and IRFlexSim. These simulatorswhich are easily integrated with other system simulators such as RSIMfacilitate the design and evaluation of multiprocessor and cluster computer communication subsystems at the level of flow control units (flits). They have seen wide use in academia both nationally and internationally and also have found use in industry at such places as HP/Compaq and Sun Microsystems. Under our current CCR supported project and in collaboration with researchers from Spain, an InfiniBand network simulator is also being developed using OPNET ModelerTM that allows detailed simulation and analysis of subnet management mechanisms and protocols currently under investigation for high-performance server I/O and intracluster communication.

High-Performance Network Architecture with Speculative Scheduling for Globally Active Congestion Control

Project Description of NSF Grant CCR-0311742

Efficient and reliable networking among communicating entities is crucial for achieving high performance. Continuing improvements in device integration and packaging technologies allow hundreds to thousands of processing nodes or Internet IP router ports to be connected through a common interconnection fabric and also enable communicating nodes to employ a greater level of execution parallelism. Along with these improvements, the emergence of bandwidth-hungry applications, e.g., high-definition video/audio-on-demand servers, on-line transaction processing and database/decision support systems, grid applications, etc., imposes even greater performance demand on the communicating network architecture, making it critical.

Whereas VLSI technology constraints determine maximum achievable network link bandwidth and network component layout constraints determine maximum achievable network bisection bandwidth, the capabilities of the routing algorithm/scheduler determine the limitations of how efficiently link/bisection bandwidth is utilized. By naively resolving structural hazards locally without a more global view, utilization of network link and bisection bandwidth becomes imbalanced, wasting valuable bandwidth. In this research, we develop new and efficient techniques for detecting and dispersing cyclic as well as non-cyclic blocking dependencies on network resources both within the network and at network endpoints.

Our approach is to add minimal intelligence (i.e., speculative scheduling capability) to routers and network interfaces such that network resources are maximally utilized and hot-spotting activity that can lead to congestion and deadlock in the network is thwarted. The proposed techniques can be used for more rapidly advancing packets directly involved in network congestion, more effectively steering packets around congestion, and more precisely detecting and efficiently resolving congestion and potential deadlock situations, including those involving message dependencieswhich has largely been neglected in past research. This acts to significantly increase the maximum sustainable throughput capabilities of a network. In addition to developing formal theoretical support for the proposed techniques, we intend to provide proof of concepts through modeling, simulation, and possibly implementation in a small-scale testbed system or using commercially available components.

The intellectual merits of this research have substantial promise. This research opens new and exciting opportunities for exploring highly sought-after load balancing capabilities that help prevent the global expansion of congestion trees/cycles by more effectively dispersing them early-on, thus averting serious performance degradation and allowing higher sustained throughput and more predictable latency. This has further significance and impact in near future systems given that, in those systems, network components are projected to operate much more closely to their saturation point: with increasing bristling factors and greater QoS traffic, the limited network bandwidth available to packets in other traffic classes will become more easily saturated, making the need for improved congestion/deadlock resolution techniques even more important. Furthermore, as high-performance network architectures endemic to tightly-coupled systems continue to become more prevalent in other systems, this research will have even more far-reaching application. For example, in networks which require a high sustained throughput regardless of traffic pattern and applied load (e.g., in supporting QoS in bandwidth-greedy server clusters or for handling IP traffic at line rates when used as the interconnect fabric within Internet routers) this research may have major impact there as well.

Index of /smart/publications/archives



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


This entry was posted on May 17, 2013 by in Computer Science, Electronic & Computer Engineering, Science & Technology.
Virtual Fashion Technology

Virtual Fashion Education


"chúng tôi chỉ là tôi tớ của anh em, vì Đức Kitô" (2Cr 4,5b)


News About Tech, Money and Innovation


Modern art using the GPU

Theme Showcase

Find the perfect theme for your blog.


Learn to Learn

Gocomay's Blog

Con tằm đến thác vẫn còn vương tơ

Toán cho Vật lý

Khoa Vật lý, Đại học Sư phạm Tp.HCM - ĐT :(08)-38352020 - 109

Maths 4 Physics & more...

Blog Toán Cao Cấp (M4Ps)

Bucket List Publications

Indulge- Travel, Adventure, & New Experiences


‎"Behind every stack of books there is a flood of knowledge."

The Blog

The latest news on and the WordPress community.

%d bloggers like this: