Browsing by Subject "Deadlock"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item B-RPM: An Efficient One-to-Many Communication Framework for On-Chip Networks(2012-10-19) Shaukat, NomanThe prevalence of multicore architectures has accentuated the need for scalable on-chip communication media. Various parallel applications and programming paradigms use a mix of unicast (one-to-one) and multicast (one-to-many) to maintain data coherence and consistency. Providing efficient support for these communication patterns becomes a critical design point for on-chip networks (OCN). High performance on-chip networks design advocates balanced traffic across the whole network, which makes adaptive routing appealing. Adaptive routing explores the path diversity of the network, increases throughput, and reduces network latency compared with oblivious routing. In this work, we propose an adaptive multicast routing, Balanced Recursive Partitioning Multicast (B-RPM), to achieve balanced one-to-many on-chip communication. The algorithm derives its functionality from previously proposed algorithm Recursive Partitioning Multicast (RPM). Unlike RPM which uses fixed set of directional priorities and position of destination nodes, B-RPM replicates packet based on the local congestion information and position of destination nodes with respect to current node. B-RPM employs a new deadlock avoidance technique Dynamically Sized Virtual Networks (DSVN). Built upon the traditional virtual networks, DSVN dynamically allocates the network resources to different VNs according to the run-time traffic status, which delivers better resources utilization. We also propose a new scheme for representing multiple destinations in packet head. The scheme works simply by differentiating multicast and unicast packets. The algorithm combined with dynamically sized virtual networks enables us to improve network performance at high load on average by 20% (up to 50%) and saturation throughput of network on average by 10% (up to 18%) over the most recent multicast algorithm. Also the new header representation scheme enables us to save 24% of dynamic link power.Item Computational process networks : a model and framework for high-throughput signal processing(2011-05) Allen, Gregory Eugene; Evans, Brian L. (Brian Lawrence), 1965-; Browne, James C.; Chase, Craig M.; John, Lizy K.; Loeffler, Charles M.Many signal and image processing systems for high-throughput, high-performance applications require concurrent implementations in order to realize desired performance. Developing software for concurrent systems is widely acknowledged to be difficult, with common industry practice leaving the burden of preventing concurrency problems on the programmer. The Kahn Process Network model provides the mathematically provable property of determinism of a program result regardless of the execution order of its processes, including concurrent execution. This model is also natural for describing streams of data samples in a signal processing system, where processes transform streams from one data type to another. However, a Kahn Process Network may require infinite memory to execute. I present the dynamic distributed deadlock detection and resolution (D4R) algorithm, which permits execution of Process Networks in bounded memory if it is possible. It detects local deadlocks in a Process Network, determines whether the deadlock can be resolved and, if so, identifies the process that must take action to resolve the deadlock. I propose the Computational Process Network (CPN) model which is based on the formalisms of Kahn’s PN model, but with enhancements that are designed to make it efficiently implementable. These enhancements include multi-token transactions to reduce execution overhead, multi-channel queues for multi-dimensional synchronous data, zero-copy semantics, and consumer and producer firing thresholds for queues. Firing thresholds enable memoryless computation of sliding window algorithms, which are common in signal processing systems. I show that the Computational Process Network model preserves the formal properties of Process Networks, while reducing the operations required to implement sliding window algorithms on continuous streams of data. I also present a high-throughput software framework that implements the Computational Process Network model using C++, and which maps naturally onto distributed targets. This framework uses POSIX threads, and can exploit parallelism in both multi-core and distributed systems. Finally, I present case studies to exercise this framework and demonstrate its performance and utility. The final case study is a three-dimensional circular convolution sonar beamformer and replica correlator, which demonstrates the high throughput and scalability of a real-time signal processing algorithm using the CPN model and framework.