The era of AI is witnessing a significant increase in energy consumption and carbon emissions from the execution of large language models (LLMs). Due to memory and compute requirements, it is necessary to distribute training and inference across many AI accelerators, such as GPUs. This paper focuses on distributed training that requires significant collective communication between accelerators; which often accounts for greater than half of training time. Besides LLMs, collective communication between GPUs is also common for many ML and HPC workloads. We first analyze the properties of collective communication operations in Nvidia Collective Communication Library (NCCL) and characterize the bandwidth, frequency, and energy properties of each collective communication operation. Then we propose PCCL, a Power-aware Collective Communication Library, based on NCCL, that can reduce power for communication kernels with dynamic voltage and frequency scaling (DVFS). PCCL identifies the optimal frequency for each collective communication call and precisely manages the GPU frequency accordingly in runtime. It can transparently lower the energy consumption of collective communication operations with negligible impact to throughput and performance. PCCL can reduce the energy of collective communication operations by ~27% and can reduce the end-to-end LLM training energy by 17.3%.

One-sided dense matrix decompositions (e.g., Cholesky, LU, and QR) are the key components in scientific computing in many different fields. Although their design has been highly optimized for modern processors, they still consume a considerable amount of energy. As CPU-GPU heterogeneous systems are commonly used for matrix decompositions, in this work, we aim to further improve the energy saving of onesided matrix decompositions on CPU-GPU heterogeneous systems. We first build an Algorithm-Based Fault Tolerance protected overclocking technique (ABFT-OC) to enable us to exploit reliable overclocking for key matrix decomposition operations. Then, we design an energy-saving matrix decomposition framework, Bi-directional Slack Reclamation (BSR), that can intelligently combine the capability provided by ABFT-OC and DVFS to maximize energy saving and maintain performance and reliability. Experiments show that BSR is able to save up to 11.7% more energy compared with the current best energy saving optimization approach with no performance degradation and up to 14.1% Energy×Delay2 reduction. Also, BSR enables the Pareto efficient performance-energy trade-off, which is able to provide up to 1.43× performance improvement without costing extra energy.

Most CPU power management techniques for web search assume that the time budget for a query is given a priori. However, determining the time budget on a per query granularity is challenging, because a difficult trade-off between the search latency, quality and power consumption has to be made. In this paper, we present Cottage, a coordinated time budget assignment framework between the aggregator and Index Serving Nodes (ISNs), which employs two distinct distributed search latency and quality predictors. The prediction results are integrated at a centralized optimizer for selecting the proper search time budget, while cutting off slow and low quality ISNs. Cottage also accelerates slow ISNs that have a high quality contribution, thus improving search quality. The implementation results on the Solr search engine show that Cottage outperforms state-of-the-art approaches with a 54% latency reduction and 41.3% less consumed power. In addition, the P@10 search quality with Cottage can still be as good as 0.947.

The 5G user plane function (UPF) is a critical inter-connection point between the data network and cellular network infrastructure. It governs the packet processing performance of the 5G core network. UPFs also need to be flexible to support several key control plane operations. Existing UPFs typically run on general-purpose CPUs, but have limited performance because of the overheads of host-based forwarding. We design Synergy, a novel 5G UPF running on SmartNICs that provides high throughput and low latency. It also supports monitoring functionality to gather critical data on user sessions for the prediction and optimization of handovers during user mobility. The SmartNIC UPF efficiently buffers data packets during handover and paging events by using a two-level flow-state access mechanism. This enables maintaining flow-state for a very large number of flows, thus providing very low latency for control and data planes and high throughput packet forwarding. Mobility prediction can reduce the handover delay by pre-populating state in the UPF and other core NFs. Synergy performs handover predictions based on an existing recurrent neural network model. Synergy's mobility predictor helps us achieve 2.32× lower average handover latency. Buffering in the SmartNIC, rather than the host, during paging and handover events reduces packet loss rate by at least 2.04×. Compared to previous approaches to building programmable switch-based UPFs, Synergy speeds up control plane operations such as handovers because of the low P4-programming latency leveraging tight coupling between SmartNIC and host.

Despite advances in network security, attacks targeting mission critical systems and applications remain a significant problem for network and datacenter providers. Existing telemetry platforms detect volumetric attacks at terabit scales using approximation techniques and coarse grain analysis. However, the prevalence of low and slow attacks that require very little bandwidth, makes flow-state tracking critical to overall attack mitigation. Traffic queries deployed on network switches are often limited by hardware constraints, preventing them from carrying out flow tracking features required to detect stealthy attacks. Such attacks can go undetected in the midst of high traffic volumes.

Data center workload fluctuations need periodic, but careful scheduling to minimize power consumption while meeting the task completion time requirements. Existing data center scheduling systems tightly pack containers to save power. However, with the growth of multi-tiered applications, there is a significant need to account for the affinity between application components, to minimize communication overheads and latency. Centralized container scheduling systems using graph partitioning algorithms cause a significant number of task migrations, with associated downtime.We design pMACH, a novel distributed container scheduling scheme for optimizing both power and task completion time in data centers. It minimizes task migrations and packs frequently communicating containers together without overloading servers. pMACH operates at peak energy efficiency, thus reducing energy consumption while also providing greater headroom for unpredictable workload spikes. We also propose in-network monitoring using smartNICs (sNIC) to measure the communications and then perform scheduling in a hierarchical, parallelized framework to achieve high performance and scalability. pMACH is based on incremental partitioning and it leverages the previous scheduling decision to significantly reduce the number of containers moved between servers, avoiding application downtime.Both testbed measurements and large-scale trace-driven simulations show that pMACH saves at least 13.44% more power compared to previous scheduling systems. It speeds task completion, reducing the 95th percentile by a factor of 1.76-2.11 compared to existing container scheduling schemes. Compared to other static graph-based approaches, our incremental partitioning technique reduces migrations per epoch by 82%.

The massive parallelism present in GPUs comes at the cost of reduced L1 and L2 cache sizes per thread, leading to serious cache contention problems such as thrashing. Hence, the data access locality of an application should be considered during thread scheduling to improve execution time and energy consumption. Recent works have tried to use the locality behavior of regular and structured applications in thread scheduling, but the difficult case of irregular and unstructured parallel applications remains to be explored. We present PAVER , a P riority- A ware V ertex schedul ER , which takes a graph-theoretic approach toward thread scheduling. We analyze the cache locality behavior among thread blocks ( TBs ) through a just-in-time compilation, and represent the problem using a graph representing the TBs and the locality among them. This graph is then partitioned to TB groups that display maximum data sharing, which are then assigned to the same streaming multiprocessor by the locality-aware TB scheduler. Through exhaustive simulation in Fermi, Pascal, and Volta architectures using a number of scheduling techniques, we show that PAVER reduces L2 accesses by 43.3%, 48.5%, and 40.21% and increases the average performance benefit by 29%, 49.1%, and 41.2% for the benchmarks with high inter-TB locality.

The leakage power dissipation has become one of the major concerns with technology scaling. The GPGPU register file has grown in size over last decade in order to support the parallel execution of thousands of threads. Given that each thread has its own dedicated set of physical registers, these registers remain idle when corresponding threads go for long latency operation. Existing research shows that the leakage energy consumption of the register file can be reduced by under volting the idle registers to a data-retentive low-leakage voltage (Drowsy Voltage) to ensure that the data is not lost while not in use. In this paper, we develop a realistic model for determining the wake-up time of registers from various under-volting and power gating modes. Next, we propose a hybrid energy saving technique where a combination of power-gating and under-volting can be used to save optimum energy depending on the idle period of the registers with a negligible performance penalty. Our simulation shows that the hybrid energy-saving technique results in 94% leakage energy savings in register files on an average when compared with the conventional clock gating technique and 9% higher leakage energy saving compared to the state-of-art technique.

The current trend of ever-increasing performance in scientific applications comes with tremendous growth in energy consumption. In this paper, we present a framework for GPU applications, which reduces energy consumption in GPUs through Safe Overclocking and Undervolting (SAOU) without sacrificing performance. The idea is to increase the frequency beyond the safe frequency fsa f eMax and undervolt below Vsa f eMin to get maximum energy saving. Since such overclocking and undervolting may give rise to faults, we employ an enhanced checkpoint-recovery technique to cover the possible errors. Empirically, we explore different errors and derive a fault model that can set the undervolting and overclocking level for maximum energy saving. We target cuBLAS Matrix Multiplication (cuBLAS-MM) kernel for error correction using the checkpoint and recovery (CR) technique as an example of scientific applications. In case of cuBLAS, SAOU achieves up to 22% energy reduction through undervolting and overclocking without sacrificing the performance.

The service quality of web search depends considerably on the request tail latency from Index Serving Nodes (ISNs), prompting data centers to operate them at low utilization and wasting server power. ISNs can be made more energy efficient utilizing Dynamic Voltage and Frequency Scaling (DVFS) or sleep states techniques to take advantage of slack in latency of search queries. However, state-of-the-art frameworks use a single distribution to predict a request's service time and select a high percentile tail latency to derive the CPU's frequency or sleep states. Unfortunately, this misses plenty of energy saving opportunities. In this paper, we develop a simple linear regression predictor to estimate each individual search request's service time, based on the length of the request's posting list. To use this prediction for power management, the major challenge lies in reducing miss rates for deadlines due to prediction errors, while improving energy efficiency. We present Swan, a two-Step poWer mAnagement for distributed search eNgines. For each request, Swan selects an initial, lower frequency to optimize power, and then appropriately boosts the CPU frequency just at the right time to meet the deadline. Additionally, we re-configure the time instant for boosting frequency, when a critical request arrives and avoid deadline violations. Swan is implemented on the widely-used Solr search engine and evaluated with two representative, large query traces. Evaluations show Swan outperforms state-of-the-art approaches, saving at least 39% CPU power on average.

Saving energy for latency-critical applications like web search can be challenging because of their strict tail latency constraints. State-of-the-art power management frameworks use Dynamic Voltage and Frequency Scaling (DVFS) and Sleep states techniques to slow down the request processing and finish the search just-in-time. However, accurately predicting the compute demand of a request can be difficult. In this paper, we present Gemini, a novel power management framework for latency-critical search engines. Gemini has two unique features to capture the per query service time variation. First, at light loads without request queuing, a two-step DVFS is used to manage the CPU power. Our two-step DVFS selects the initial CPU frequency based on the query specific service time prediction and then judiciously boosts the initial frequency at the right time to catch-up to the deadline. The determination of boosting time further relies on estimating the error in the prediction of individual query's service time. At high loads, where there is request queuing, only the current request being executed and the critical request in the queue adopt a two-step DVFS. All the other requests in-between use the same frequency to reduce the frequency transition overhead. Second, we develop two separate neural network models, one for predicting the service time and the other for the error in the prediction. The combination of these two predictors significantly improves the power saving and tail latency results of our two-step DVFS. Gemini is implemented on the Solr search engine. Evaluations on three representative query traces show that Gemini saves 41% of the CPU power, and is better than other state-of-the-art techniques.

The complex, distributed nature of data centers have spawned the adoption of distributed, multi-tiered software architectures, consisting of many inter-connected microservices. These microservices exhibit extremely short request service times, often less than 250μs. We show that these “killer microsecond” service times can cause state-of-the-art dynamic power management techniques to break down, due to short idle period length and low power state transition overheads. In this paper, we propose μDPM, a dynamic power management scheme for the microsecond era that coordinates request delaying, per-core sleep states, and voltage frequency scaling. The idea is to postpone the wake up of a CPU as long as possible and then adjust the frequency so that the tail latency constraint of requests are satisfied just-in-time. μDPM reduces processor energy consumption by up to 32% and consistently outperforms state-of-the-art techniques by 2×.

Power management in data centers is challenging because of fluctuating workloads and strict task completion time requirements. Recent resource provisioning systems, such as Borg and RC-Informed, pack tasks on servers to save power. However, current power optimization frameworks based on packing leave very little headroom for spikes, and the task completion times are compromised. In this paper, we design Goldilocks, a novel resource provisioning system for optimizing both power and task completion time by allocating tasks to servers in groups. Tasks hosted in containers are grouped together by running a graph partitioning algorithm. Containers communicating frequently are placed together, which improves the task completion times. We also leverage new findings on power consumption of modern-day servers to ensure that their utilizations are in a range where they are power-proportional. Both testbed implementation measurements and large-scale trace-driven simulations prove that Goldilocks outperforms all the previous works on data center power saving. Goldilocks saves power by 11.7%-26.2% depending on the workload, whereas the best of the implemented alternatives, Borg, saves 8.9%-22.8%. The energy per request for the Twitter content caching workload in Goldilocks is only 33% of RC-Informed. Finally, the best alternative in terms of task completion time, E-PVM, has 1.17-3.29 times higher task completion times than Goldilocks across different workloads.

The current trend of ever-increasing performance in scientific applications comes with tremendous growth in energy consumption. In this paper, we present GreenMM framework for matrix multiplication, which reduces energy consumption in GPUs through undervolting without sacrificing the performance. The idea in this paper is to undervolt the GPU beyond the minimum operating voltage (Vmin) to save maximum energy while keeping the frequency constant. Since such undervolting may give rise to faults, we design an Algorithm Based Fault Tolerance (ABFT) algorithm to detect and correct those errors. We target cuBLAS Matrix Multiplication (cuBLAS-MM), as a key kernel used in many scientific applications. Empirically, we explore different errors and derive a fault model as a function of undervolting levels and matrix sizes. Then, using the model, we configure the proposed FT-cuBLAS-MM algorithm. We show that energy consumption is reduced up to 19.8%. GreenMM also improves the GFLOPS/Watt by 9% with negligible performance overhead.

GPGPUs are now commonly used as co-processors of CPUs for the computation of data parallel and throughputintensive algorithms. However, memory available in GPGPUs is limited for many applications of interest; there is a continuous demand for increased memory of such applications. Several techniques like multi-steaming or pinned memory are frequently employed to mitigate these issues to some extent. However, these techniques either suffer from latency overhead or increase programming complexity. GPUdmm uses GPU DRAM as a cache of CPU; key problems in this design are inefficient memory access data-path and tag access overhead. In this context, we present CAMO, a novel cache memory organization for GPGPUs which addresses the limitations of pinned memory technique and GPUdmm. First, it uses GPU DRAM as a victim cache of LLC that improves the performance by delivering data faster to the SMs. Second, it uses ATCache, a CPU based DRAM cache tag management technique. ATCache reduces the number of DRAM cache accesses. We implement CAMO within the GPGPU-Sim framework and show that its average performance - when compared with pinned memory - increases by a factor of 1.87x and the peak performance growth being 4.67x. In addition, CAMO outperforms GPUdmm on an average by a factor of 15.9% and maximum speedup by a factor of 80%.

Achieving energy proportionality in data centers supporting latency-sensitive applications is challenging because of the strict Service Level Agreements. Previous works individually focus on making the server energy proportional or reducing the data center network's power consumption for latency-tolerant applications. In this paper, we propose EPRONS to minimize the overall data center's power consumption with latency-sensitive applications by trading-off network slack in favor of providing additional slack for computations. We utilize the linear programming model to consolidate latency-sensitive search queries and latency-tolerant background flows to a minimal subnet of the topology by turning off unused switches and links without violating the application deadlines. Servers take advantage of the additional 'network-provided' slack to allow slowing down request processing. For servers, we design a novel power saving technique using Dynamic Voltage and Frequency Scaling (DVFS) based on the average tail latency of a request. If needed, we turn on a minimal number of additional network links and switches to reduce network latency while still maximizing entire data center's power saving. Experimental results show that our scheme saves up to 31.25% of a data center's total power budget.

Scientific applications with single instruction, multiple data (SIMD) computations show considerable performance improvements when run on today's graphics processing units (GPUs). However, the existence of data dependences across thread blocks may significantly impact the speedup by requiring global synchronization across multiprocessors (SMs) inside the GPU. To efficiently run applications with interblock data dependences, we need fine-granular task-based execution models that will treat SMs inside a GPU as stand-alone parallel processing units. Such a scheme will enable faster execution by utilizing all internal computation elements inside the GPU and eliminating unnecessary waits during device-wide global barriers.

Web search constitutes an important class of data-intensive online services in data centers. Optimizing search systems for energy efficiency, timely response and high search quality (i.e., how relevant the returned results are to a search query), however, is very challenging, as a search system involves a distributed architecture with hundreds of thousands of index serving nodes (ISNs) that return searching results to an aggregator through multiple interdependent retrieval stages in a partition-aggregate fashion. In this paper, we discover through experiments two important characteristics that can affect the system performance: (1) response time and energy consumption are greatly impacted by a small fraction of queries with long processing times; (2) the quality contribution of the ISN is independent of the query processing time. Based on our observation, we propose TailCut, which judiciously discards long query executions and enables ISN-aggregator coordination to minimize energy consumption subject to latency and quality constraints. Our experimental results show that TailCut can achieve up to 39% power saving, while satisfying the tail latency and quality constraint.

GPUs lack fundamental support for data-dependent parallelism and synchronization. While CUDA Dynamic Parallelism signals progress in this direction, many limitations and challenges still remain. This paper introduces Wireframe, a hardware-software solution that enables generalized support for data-dependent parallelism and synchronization. Wireframe enables applications to naturally express execution dependencies across different thread blocks through a dependency graph abstraction at run-time, which is sent to the GPU hardware at kernel launch. At run-time, the hardware enforces the dependencies specified in the dependency graph through a dependency-aware thread block scheduler. Overall, Wireframe is able to improve total execution time up to 65.20% with an average of 45.07%.

Recent generations of GPUs and their corresponding APIs provide means for sharing compute resources among multiple applications with greater efficiency than ever. This advance has enabled the GPUs to act as shared computation resources in multi-user environments, like supercomputers and cloud computing. Recent research has focused on maximizing the utilization of GPU computing resources by simultaneously executing multiple GPU applications (i.e., concurrent kernels) via temporal or spatial partitioning. However, they have not considered maximizing the utilization of the PCI-e bus which is equally important as applications spend a considerable amount of time on data transfers.

Nested patterns are one of the most frequently occurring algorithmic themes in GPU applications where coarse-grained tasks are constituted from a number of fine-grained ones. However, efficient execution of irregular nested patterns, with coarse-grained tasks that substantially vary in size, has remained an open problem for the GPU's SIMT architecture. Existing methods rely on static task decomposition where one or a fixed number of threads inside the SIMD grouping (warp) carry out the fine-grained tasks. These approaches fail to provide portable performance across diversity of irregular inputs. Moreover, due to intra-warp load imbalance, they incur warp underutilization. In this paper, we introduce a novel software technique called Collaborative Task Engagement (CTE) that, unlike previous methods, achieves sustained high warp execution efficiencies across irregular inputs and provides portable performance. CTE assigns a group of coarse-grained tasks to the warp and allows threads inside the warp carry out the expanded list of fine-grained tasks collaboratively. In multiple rounds, all the warp threads perform mapping portion of fine-grained tasks and participate in a reduction phase with appropriate lanes to reduce calculated values. This scheme avoids over-subscription or under-subscription of threads while preserving the benefits of parallel reduction. We prepared a CUDA C++ device-side template library for developers to easily express nested patterns in GPU kernels using our technique. Our experiments show that CTE delivers up to 37% warp execution efficiency improvement and gives up to 1.51x speedup over sub-warp decomposition with the best sub-warp width.

Servers running in datacenters are commonly kept underutilized to meet stringent latency targets. Due to poor energy-proportionality in commodity servers, the low utilization results in wasteful power consumption that cost millions of dollars. Applying dynamic power management on datacenter workloads is challenging, especially when tail latency requirements often fall in the sub-millisecond level. The fundamental issue is randomness due to unpredictable request arrival times and request service times. Prior techniques applied per-core DVFS to have fine-grain control of slowing down request processing without violating the tail latency target. However, most commodity servers only support per-core DFS, which greatly limits potential energy saving. In this paper, we propose DynSleep, a fine-grain power management scheme for datacenter workloads through the use of per-core sleep states (C-states). DynSleep dynamically postpones the processing of some requests, creating longer idle periods, which allow the use of deeper C-states to save energy. We design and implement DynSleep with Mem-cached, a popular key-value store application used in datacenters. The experimental results show that DynSleep achieves up to 65% core power saving, and 27% better than the per-core DVFS power management scheme, while still satisfying the tail latency constraint. To the best of our knowledge, this is the first work to analyze and develop power management technique with CPU C-states in latency-critical datacenter workloads

While many linear algebra libraries have been developed to optimize their performance, no linear algebra library considers their energy efficiency at the library design time. In this paper, we present GreenLA - an energy efficient linear algebra software package that leverages linear algebra algorithmic characteristics to maximize energy savings with negligible overhead. GreenLA is (1) energy efficient: it saves up to several times more energy than the best existing energy saving approaches that do not modify library source codes; (2) high performance: its performance is comparable to the highly optimized linear algebra library MAGMA; and (3) transparent to applications: with the same programming interface, existing MAGMA users do not need to modify their source codes to benefit from GreenLA. Experimental results demonstrate that GreenLA is able to save up to three times more energy than the best existing energy saving approaches while delivering similar performance compared to the state-of-the-art linear algebra library MAGMA.

Schedulers used by modern OSs (e.g., Oracle Solaris 11™ and GNU/Linux) balance load by balancing the number of threads in run queues of different cores. While this approach is effective for a single CPU multicore system, we show that it can lead to a significant load imbalance across CPUs of a multi-CPU multicore system. Because different threads of a multithreaded application often exhibit different levels of CPU utilization, load cannot be measured in terms of the number of threads alone. We propose Tumbler that migrates the threads of a multithreaded program across multiple CPUs to balance the load across the CPUs. While Tumbler distributes the threads equally across the CPUs, its assignment of threads to CPUs is aimed at minimizing the variation in utilization of different CPUs to achieve load balance. We evaluated Tumbler using a wide variety of 35 multithreaded applications, and our experimental results show that Tumbler outperforms both Oracle Solaris 11™ and GNU/Linux.

Hashing is one of the most fundamental operations that provides a means for a program to obtain fast access to large amounts of data. Despite the emergence of GPUs as many-threaded general purpose processors, high performance parallel data hashing solutions for GPUs are yet to receive adequate attention. Existing hashing solutions for GPUs not only impose restrictions (e.g., inability to concurrently execute insertion and retrieval operations, limitation on the size of key-value data pairs) that limit their applicability, their performance does not scale to large hash tables that must be kept out-of-core in the host memory. In this paper we present Stadium Hashing (Stash) that is scalable to large hash tables and practical as it does not impose the aforementioned restrictions. To support large out-of-core hash tables, Stash uses a compact data structure named ticket-board that is separate from hash table buckets and is held inside GPU global memory. Ticket-board locally resolves significant portion of insertion and lookup operations and hence, by reducing accesses to the host memory, it accelerates the execution of these operations. Split design of the ticket-board also enables arbitrarily large keys and values. Unlike existing methods, Stash naturally supports concurrent insertions and retrievals due to its use of double hashing as the collision resolution strategy. Furthermore, we propose Stash with collaborative lanes (clStash) that enhances GPU's SIMD resource utilization for batched insertions during hash table creation. For concurrent insertion and retrieval streams, Stadium hashing can be up to 2 and 3 times faster than GPU Cuckoo hashing for in-core and out-of-core tables respectively.

The vast computing power of GPUs makes them an attractive platform for accelerating large scale data parallel computations such as popular graph processing applications. However, the inherent irregularity and large sizes of real-world power law graphs makes effective use of GPUs a major challenge. In this paper we develop techniques that greatly enhance the performance and scalability of vertex-centric graph processing on GPUs. First, we present Warp Segmentation, a novel method that greatly enhances GPU device utilization by dynamically assigning appropriate number of SIMD threads to process a vertex with irregular-sized neighbors while employing compact CSR representation to maximize the graph size that can be kept inside the GPU global memory. Prior works can either maximize graph sizes (VWC uses the CSR representation) or device utilization (e.g., CuSha uses the CW representation, however, CW is roughly 2.5x the size of CSR). Second, we further scale graph processing to make use of multiple GPUs while proposing Vertex Refinement to address the challenge of judiciously using the limited bandwidth available for transferring data between GPUs via the PCIe bus. Vertex refinement employs parallel binary prefix sum to dynamically collect only the updated boundary vertices inside GPUs' outbox buffers for dramatically reducing inter-GPU data transfer volume. Whereas existing multi-GPU techniques (Medusa, TOTEM) perform high degree of wasteful vertex transfers. On a single GPU, our framework delivers average speedups of 1.29x to 2.80x over VWC. When scaled to multiple GPUs, our framework achieves up to 2.71x performance improvement compared to inter-GPU vertex communication schemes used by other multi-GPU techniques (i.e., Medusa, TOTEM).

As processor power density increases, thermal and power control becomes critical for application processing. In this paper, we consider network applications which feature ON/OFF execution pattern, that causes frequent temperature and power consumption changes in the processor. A novel power aware thermal management algorithm is designed to achieve power saving in multicore processors by employing a vacation scheme. We implement the scheme through the idle states (C-state) provided by the OS in the CPU and show their effectiveness both through analysis and experimental data. Then, we apply our scheme with the thermal constraint and propose a heterogeneous load distribution, which creates more opportunities for power saving. Besides maintaining processor temperature below the temperature constraint, our technique achieves higher sustainable load and better power saving with minimum latency increase compared to existing thermal management techniques. To the best of our knowledge, this is the first work to discuss and develop vacation algorithm considering power, temperature and latency for network application on a general purpose multicore processor.

Nested loops with regular iteration dependencies span a large class of applications ranging from string matching to linear system solvers. Wavefront parallelism is a well-known technique to enable concurrent processing of such applications and is widely being used on GPUs to benefit from their massively parallel computing capabilities. Wavefront parallelism on GPUs uses global barriers between processing of tiles to enforce data dependencies. However, such diagonal-wide synchronization causes load imbalance by forcing SMs to wait for the completion of the SM with longest computation. Moreover, diagonal processing causes loss of locality due to elements that border adjacent tiles.

GPU's SIMD architecture is a double-edged sword confronting parallel tasks with control flow divergence. On the one hand, it provides a high performance yet power-efficient platform to accelerate applications via massive parallelism; however, on the other hand, irregularities induce inefficiencies due to the warp's lockstep traversal of all diverging execution paths. In this work, we present a software (compiler) technique named Collaborative Context Collection (CCC) that increases the warp execution efficiency when faced with thread divergence incurred either by different intra-warp task assignment or by intra-warp load imbalance. CCC collects the relevant registers of divergent threads in a warp-specific stack allocated in the fast shared memory, and restores them only when the perfect utilization of warp lanes becomes feasible. We propose code transformations to enable applicability of CCC to variety of program segments with thread divergence. We also introduce optimizations to reduce the cost of CCC and to avoid device occupancy limitation or memory divergence. We have developed a framework that automates application of CCC to CUDA generated intermediate PTX code. We evaluated CCC on real-world applications and multiple scenarios using synthetic programs. CCC improves the warp execution efficiency of real-world benchmarks by up to 56% and achieves an average speedup of 1.69x (maximum 3.08x).

On a cache-coherent multicore multiprocessor system, the performance of a multithreaded application with high lock contention is very sensitive to the distribution of application threads across multiple processors (or Sockets). This is because the distribution of threads impacts the frequency of lock transfers between Sockets, which in turn impacts the frequency of last-level cache (LLC) misses that lie on the critical path of execution. Since the latency of a LLC miss is high, an increase of LLC misses on the critical path increases both lock acquisition latency and critical section processing time. However, thread schedulers for operating systems, such as Solaris and Linux, are oblivious of the lock contention among multiple threads belonging to an application and therefore fail to deliver high performance for multithreaded applications.

As processor power density increases, thermal and power control becomes critical for packet processing on a processor. In "run-to-finish" applications, power consumption is stable and temperature simply rises to saturation point and then stabilizes. But, network applications feature ON/OFF execution pattern, which causes frequent temperature and power consumption changes in the processor. We propose a thermal aware scheduler, TrafficLight, which achieves power saving by employing vacation and rate adaptation techniques. We implement these through the idle states (C-state) provided by the OS in a CPU and show their effec-tiveness through experimental data. Then we build power, thermal and latency models based on the vacation queuing theory, which estimates the performance of our proposed techniques. Finally, we design, implement and evaluate an on-line algorithm to dynamically choose the proper pow-er/thermal management technique based on the traffic variation. The technique maintains the processor temperature below the temperature constraint and achieves power saving. To the best of our knowledge, this is the first work to provide the theoretical analysis as well as the experimental results for the vacation and rate adaptation schemes considering power, temperature and latency in the packet processing on a general purpose processor.

Vertex-centric graph processing is employed by many popular algorithms (e.g., PageRank) due to its simplicity and efficient use of asynchronous parallelism. The high compute power provided by SIMT architecture presents an opportunity for accelerating these algorithms using GPUs. Prior works of graph processing on a GPU employ Compressed Sparse Row (CSR) form for its space-efficiency; however, CSR suffers from irregular memory accesses and GPU underutilization that limit its performance. In this paper, we present CuSha, a CUDA-based graph processing framework that overcomes the above obstacle via use of two novel graph representations: G-Shards and Concatenated Windows (CW). G-Shards uses a concept recently introduced for non-GPU systems that organizes a graph into autonomous sets of ordered edges called shards. CuSha's mapping of GPU hardware resources on to shards allows fully coalesced memory accesses. CW is a novel representation that enhances the use of shards to achieve higher GPU utilization for processing sparse graphs. Finally, CuSha fully utilizes the GPU power by processing multiple shards in parallel on GPU's streaming multiprocessors. For ease of programming, CuSha allows the user to define the vertex-centric computation and plug it into its framework for parallel processing of large graphs. Our experiments show that CuSha provides significant speedups over the state-of-the-art CSR-based virtual warp-centric method for processing graphs on GPUs.

The popular wave front parallelization has been proposed to encode H.264/AVC video employing macro-block level parallelism. This approach, however, fails to achieve an optimum performance due to a significant overhead of barrier-based synchronization. All threads must wait for the slowest ones to complete encoding before starting a next processing wave. In this paper, we propose a dynamic scheduling for parallel encoding without employing the barrier synchronization. In this approach, current threads will 1) keep recursively encoding any new ready macro-blocks, and; 2) load-balance any other ready ones to a global shared queue, which is accessed by all threads. We further propose an adaptive dynamic scheduling to mitigate the access contention at the global queue, and considers cache locality with due to the underlying hierarchical core/cache topology. The adaptive dynamic scheduling employs multiple distributed queues, and schedule tasks. To achieve both locality and load balance, neighboring macro-blocks are preferably scheduled to nearby cores. We design, implement, and evaluate our scheme on a 32-core SGI server. Running real benchmarks, we observe that our scheme outperforms wave front parallelization by 200%, and achieves 65% to 70% of the maximum encoding speedup.

Existing scheduling schemes for decoding H.264/AVC multiple streams on multi-core are largely limited by ineffective use of multi-core architecture. Among the reasons are inefficient load balancing, in which common load metrics (e.g. tasks, frames, bytes) are unable to correctly reflect processing load at cores, unscalability of scheduling algorithms for a large scale multi-core, and bottlenecks at schedulers for multi-stream decoding. In this paper, we propose a scalable adaptive Highest Random Weight (HA-HRW) hash scheduler for distributed shared memory multi-core architecture considering the following: 1) memory access and core/cache topology of the multi-core architecture; 2) appropriate processing time load metric to enforce a true load balancing; 3) hierarchical parallel scheduling to decode multiple streams simultaneously; 4) locality characteristics of processing unit candidate to limit search within neighboring cores to enable scalable scheduling. We implement and evaluate our approach on a 32-core SGI server with realistic workload. Comparing with existing schemes, our scheme achieves higher throughput, better load balancing, better CPU utilization, and no jitter problem. Our scheme scales with multi-core and multiple streams as its time complexity is O(1).

This paper discusses scheduling issues of multi-server systems. There are three desirable properties of multi-server scheduling: load balancing, fairness and locality. The three properties are often conflicting with each other. There is no scheduling scheme that possesses all the three properties. In this paper, we first propose the fairness-aware highest random weight (fHRW) scheduling algorithm as an attempt to achieve fairness and locality. fHRWtries to service packets proportionally according to priorities of flows and schedule the packets from the same flow onto the same server. Then, we solve the imbalanced load issue of fHRW by improving the hash function HRW to an adaptive HRW (AHRW). fAHRW is more efficient (in terms of load balancing) and fair than fHRW, but it still may suffer unfairness in some cases. We further enhance fAHRW to fAHRW+by proposing a new hash function AHRW+that considers fairness as well as locality. Extensive simulations have been carried out to evaluate the performance of fAHRW+. The results show that fAHRW+can provide good load balancing, locality and fairness.

On a cache-coherent multicore multiprocessor system, the performance of a multithreaded application with high lock contention is very sensitive to the distribution of application threads across multiple processors. This is because the distribution of threads impacts the frequency of lock transfers between processors, which in turn impacts the frequency of last-level cache (LLC) misses that lie on the critical path of execution. Inappropriate distribution of threads across processors increases LLC misses in the critical path and significantly degrades performance of multithreaded programs. To alleviate the above problem, this paper overviews a thread migration technique, which migrates threads of a multithreaded program across multicore processors so that threads seeking locks are more likely to find the locks on the same processor.

As processor power density increases, chip/core temperature control becomes critical for building multicore systems. This paper addresses the problem of inter-core thermal coupling and periodic thermal variation while executing multi-threaded network applications in a multicore architecture.

Domain-disparity between CPU and Hardware Accelerators(HA) leads to CPU under-utilization and inter-domain data copy overheads. By exposing HA memory to OS and host MMU, these overheads can be eliminated. In this paper, we present a shared virtual memory real system design for PCIe-based HAs to enable parallel heterogeneous execution in CPU and HAs without driver overheads. We extend Linux with a custom memory manager and scheduler to manage HA memory and application-cores respectively. Our FPGA-based multi-application logic design supports simultaneous execution of multiple heterogeneous applications. We show the advantages of heterogeneous execution and analyze how our design reduces OS overhead.

The disparity between the CPU and GPU domains has forced the programmers to adhere to the traditional driver-based GPU programming approach. The negative implications of this approach are inter-domain data transfer overhead, host memory pressure and CPU underutilization. In this paper, we propose a novel hybrid shared memory-based execution approach to enhance the throughput of the General Purpose GPU(GPGPU) applications. To achive optimal GPU execution, we adopted a midway approach between the shared memory and traditional disjoint memory GPU programming approach. Our design involves OS enhancements and extensions to an OS-integrated open-source GPU driver(GDev) which together provide the GPU application a shared memory execution platform. Our design not only eliminates several drawbacks associated with the traditional GPU programming approach, but allows data-parallel execution across CPUs and GPU.

Today's heterogeneous architectures bring together multiple general-purpose CPUs and multiple domain-specific GPUs and FPGAs to provide dramatic speedup for many applications. However, the challenge lies in utilizing these heterogeneous processors to optimize overall application performance by minimizing workload completion time. Operating system and application development for these systems is in their infancy. In this article, we propose a new scheduling and workload balancing scheme, HDSS, for execution of loops having dependent or independent iterations on heterogeneous multiprocessor systems. The new algorithm dynamically learns the computational power of each processor during an adaptive phase and then schedules the remainder of the workload using a weighted self-scheduling scheme during the completion phase. Different from previous studies, our scheme uniquely considers the runtime effects of block sizes on the performance for heterogeneous multiprocessors. It finds the right trade-off between large and small block sizes to maintain balanced workload while keeping the accelerator utilization at maximum. Our algorithm does not require offline training or architecture-specific parameters. We have evaluated our scheme on two different heterogeneous architectures: AMD 64-core Bulldozer system with nVidia Fermi C2050 GPU and Intel Xeon 32-core SGI Altix 4700 supercomputer with Xilinx Virtex 4 FPGAs. The experimental results show that our new scheduling algorithm can achieve performance improvements up to over 200% when compared to the closest existing load balancing scheme. Our algorithm also achieves full processor utilization with all processors completing at nearly the same time which is significantly better than alternative current approaches.

Since multicore systems offer greater performance via parallelism, future computing is progressing towards use of multicore machines with large number of cores. However, the performance of emerging multithreaded programs often does not scale to fully utilize the available cores. Therefore, simultaneously running multiple multithreaded applications becomes inevitable to fully exploit the computing potential of such machines. However, maximizing the performance and throughput on multicore machines in the presence of multiple multithreaded programs is a challenge for the OS. We have observed that the state-of-the-art contention management algorithms fail to effectively coschedule multithreaded programs on multicore machines. To address the above challenge, we present ADAPT, a scheduling framework that continuously monitors the resource usage of multithreaded programs and adaptively coschedules them such that they interfere with each other's performance as little as possible. In addition, ADAPT selects appropriate memory allocation and scheduling policies according to the workload characteristics. We have implemented ADAPT on a 64-core Supermicro server running Solaris 11 and evaluated it using 26 multithreaded programs including the TATP database application, SPECjbb2005, and programs from Phoenix, PARSEC, and SPEC OMP suites. The experimental results show that ADAPT substantially improves total turnaround time and system utilization relative to the default Solaris 11 scheduler.

In this paper, we design, implement, and evaluate a traffic-aware and power-efficient multicore server system by translating incoming traffic rate to appropriate system operating level, which is then translated to optimal per-core frequency configuration. According to the varying traffic rate, the system can adjust the number of active cores and per-core frequency "on-the-fly" via the use of per-core DVFS, power gating, and power migration techniques based on our new power model which considers both dynamic and static power consumption of all cores. Results on an AMD machine with two Quad-Core Opteron 2350 processors for six real network applications chosen from NetBench [19] show that our scheme reduces power consumption by an average of 41.0% compared to running with full capacity without any reduction in throughput. It also consumes less power than three other approaches, chip-wide DVFS [22], power gating [17], and chip-wide DVFS + power gating [15], by 35.2%, 24.3%, and 10.5% respectively.

Parallelizing H.264/AVC decoding on multicore architectures is challenged by its inherent structural and functional dependencies at both frame and macro-block levels, as macro-blocks and certain frame types must be decoded in a sequential order. So far, dynamic scheduling scheme with recursive tail submit, as one of the best existing algorithms, provides a good throughput performance by exploiting macro-block level parallelism and mitigating global queue contention. Nevertheless, it fails to achieve an optimal performance due to 1) the use of global queue, which incurs substantial synchronization overhead when the number of cores increases and 2) the unawareness of cache locality with respect to the underlying hierarchical core/cache topology that results in unnecessary latency, communication cost and load imbalance. In this paper, we propose an adaptive dynamic scheduling scheme that employs multiple local queues to reduce lock contention, and assigns tasks in a cache locality aware and load-balancing fashion so that neighboring macro-blocks are preferably dispatched to nearby cores. We design, implement and evaluate our scheme on a 32-core cc-NUMA SGI server. Compared to existing alternatives by running real benchmark applications, we observe that our scheme produces higher throughput and lower latency with more balanced workload and less communication cost.

Hierarchical or pyramid search is a widely used approach in motion estimation, a most expensive function in video encoding, for its low computational complexity and high efficiency. In this approach, multiple down-sampled resolutions from video frames are created. An initial motion estimation is quickly made at a lowest resolution. The final motion estimation result is achieved by propagating the initial estimation towards the original resolution. GPU or General purpose GPU embedded hundreds of number of SIMD-based cores is best suitable for motion estimation, especially with full-search-based approaches as the process can be efficiently parallelized. However, a common fundamental drawback of the hierarchical search is the erroneous estimation from the reduced resolutions may cause the final motion estimation inaccurate. Multiple-candidate motion vector approaches are proposed, however, they lack a mechanism to select the best multiple-candidate schemes considering diverse video encoding characteristics. In this paper we analyse and verify the computational complexity of the hierarchical search using NVIDIA's GPU with realistic workloads. Based on this analysis, we propose an efficient dynamic multiple-candidate motion vector approach to dynamically select best multiple-candidate motion vector schemes at runtime. This approach can achieve highest possible speedups and satisfy a desire motion estimation efficiency. Experiments on realistic workloads show the dynamic scheme selection outperforms the fixed scheme selection based on profiling.

Traditional network processors (NPs) adopt pull model, where NP cores pull packet data from external memory to local memory, triggered by cache miss or fetch instructions. Due to the long latency of data fetching, hardware multithreading is typically used to reduce the waiting time. Multithreading incurs context switch overhead, leading to inefficiency in payload processing applications. We propose a push model for future NP's architectural design to increase throughput and decrease processing delay. A hardware push unit helps to move the segments of a packet to a core's local memory to reduce hardware thread switching. Theoretical analyses are given to compare the pull and push model's performance. Further, we selected our FPGA based THNPU NP platform for verification. Experimental results indicate that the push model not only improves the system throughput, but also reduces the delay, with only a fraction of logic gate increase.

This paper overviews the first speculative parallelization technique for GPUs that can exploit parallelism in loops even in the presence of dynamic irregularities that may give rise to cross-iteration dependences. The execution of a speculatively parallelized loop consists of five phases: scheduling, computation, misspeculation check, result committing, and misspeculation recovery. We perform misspeculation check on the GPU to minimize its cost. We optimize the procedures of result committing and misspeculation recovery to reduce the result copying and recovery overhead. Finally, the scheduling policies are designed according to the types of cross-iteration dependences to reduce the misspeculation rate. Our preliminary evaluation was conducted on an nVidia Tesla C1060 hosted in an Intel(R) Xeon(R) E5540 machine. We use three benchmarks of which two contain irregular memory accesses and one contain irregular control flows that can give rise to cross-iteration dependences. Our implementation achieves 3.6x-13.8x speedups for loops in these benchmarks.

To realize the performance potential of multicore systems, we must effectively manage the interactions between memory reference behavior and the operating system policies for thread scheduling and migration decisions. We observe that these interactions lead to significant variations in the performance of a given application, from one execution to the next, even when the program input remains unchanged and no other applications are being run on the system. Our experiments with multithreaded programs, including the TATP database application, SPECjbb2005, and a subset of PARSEC and SPEC OMP programs, on a 24-core Dell PowerEdge R905 server running OpenSolaris confirms the above observation. In this work we develop Thread Tranquilizer, an automatic technique for simultaneously reducing performance variation and improving performance by dynamically choosing appropriate memory allocation and process scheduling policies. Thread Tranquilizer uses simple utilities available on modern Operating Systems for monitoring cache misses and thread context-switches and then utilizes the collected information to dynamically select appropriate memory allocation and scheduling policies. In our experiments, Thread Tranquilizer yields up to 98% (average 68%) reduction in performance variation and up to 43% (average 15%) improvement in performance over default policies of OpenSolaris. We also demonstrate that Thread Tranquilizer simultaneously reduces performance variation and improves performance of the programs on Linux. Thread Tranquilizer is easy to use as it does not require any changes to the application source code or the OS kernel.

Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N^2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 {\rm ms}, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10^{ - 6}) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations.

L7-filter is a significant deep packet inspection (DPI) extension to Netfilter in Linux's QoS framework. It classifies network traffic based on information hidden in the packet payload. Although the computationally intensive payload classification can be accelerated with multiple processors, the default OS scheduler is oblivious to both the software characteristics and the underlying multicore architecture. In this paper, we present a parallelized L7-filter algorithm and an efficient scheduler technique for multicore servers. Our multithreaded L7-filter algorithm can process the incoming packets on multiple servers boosting the throughput tremendously. Our scheduling algorithm is based on Highest Random Weight (HRW), which maintains the connection locality for the incoming traffic, but only guarantees load balance at the connection level. We present an Adapted Highest Random Weight (AHRW) algorithm that enhances HRW by applying packet-level load balancing with an additional feedback vector corresponding to the queue length at each processor. We further introduce a Hierarchical AHRW (AHRW-tree) algorithm that considers characteristics of the multicore architecture such as cache and hardware topology by developing a hash tree architecture. The algorithm reduces the scheduling overhead toO(logN) instead ofO(N) and produces a better balance between locality and load balancing. Results show that the AHRW-tree scheduler can improve the L7-filter throughput by about 50% on a Sun-Niagara-2-based server compared to a connection locality-based scheduler. Although extensively tested for L7-filter traces, our technique is applicable to many other packet processing applications, where connection locality and load balancing are important while executing on multiple processors. With these speedups and inherent software flexibility, our design and implementation provide a cost-effective alternative to the traffic monitoring and filtering ASICs.

A fundamental challenge of supporting mutable data replication in a Peer-to-Peer (P2P) system is to efficiently maintain consistency. This paper presents a framework for Balanced Consistency Maintenance (BCoM) in structured P2P systems with heterogeneous node capabilities and various workload patterns. Replica nodes of each object are organized into a tree structure for disseminating updates, and a sliding window update protocol is developed for consistency maintenance. We present an analytical model to optimize the window size according to the dynamic network conditions, workload patterns and resource limits. In this way, BCoM balances the consistency strictness, object availability for updates, and update propagation performance for various application requirements. On top of the dissemination tree, two enhancements are proposed: (1) a fast recovery scheme to strengthen the robustness against node and link failures, and (2) a node migration policy to remove and prevent bottlenecks allowing more efficient update delivery. Simulations are conducted using P2PSim to evaluate BCoM in comparison to SCOPE [1]. The experimental results demonstrate that BCoM outperforms SCOPE with lower discard rates. BCoM achieves a discard rate as low as 5 percent in most cases while SCOPE has almost 100 percent discard rate.

Efficient contention management is the key to achieving scalable performance for multithreaded applications running on multicore systems. However, contention management policies provided by modern operating systems increase context-switches and lead to performance degradation for multithreaded applications under high loads. Moreover, this problem is exacerbated by the interaction between contention management policies and OS scheduling polices. Time Share (TS) is the default scheduling policy in a modern OS such as Open Solaris and with TS policy, priorities of threads change very frequently for balancing load and providing fairness in scheduling. Due to the frequent ping-ponging of priorities, threads of an application are often preempted by the threads of the same application. This increases the frequency of involuntary context-switches as wells as lock-holder thread preemptions and leads to poor performance. This problem becomes very serious under high loads. To alleviate this problem, in this paper, we present a scheduling policy called Faithful Scheduling (FF), which dramatically reduces context-switches as well as lock-holder thread preemptions. We implemented FF on a 24-core Dell Power Edge R905 server running OpenSolaris.2009.06 and evaluated it using 22 programs including the TATP database application, SPECjbb2005, programs from PARSEC, SPEC OMP, and some micro benchmarks. The experimental results show that FF policy achieves high performance for both lightly and heavily loaded systems. Moreover it does not require any changes to the application source code or the OS kernel.

As processor power density has increased at an alarming rate, chip/core temperature control becomes critical in satisfying given thermal constraint and avoiding hotspots. Unlike "run-to-finish" applications whose temperature will simply rise to saturation point and then stabilize, network applications do periodic packet processing, which causes temperature to rise and fall over time. However, no existing studies have focused on characterizing the temperature variation for periodic tasks. We envision that volatile thermal behavior has to be well understood in order to optimize thermal management. In this paper, we first build a novel predictive thermal model for generic periodic tasks running on a single core. This model can dynamically derive the core temperature at any time quickly and accurately. To verify the model, we use both Hot Spot simulator and a real Linux machine to run six network applications chosen from Net Bench. Then, we propose an online model update strategy using on-chip thermal sensors, which can effectively correct incidental errors by adjusting model parameters "on-the-fly". Finally, by combining the thermal model and the online update, we design, implement and evaluate a predictive model-based thermal management scheme on an Intel Xeon E5335 core for network applications based on the Stop & Go technique. Compared with two other alternatives, our scheme achieves lower temperature, higher throughput, no thermal constraint violation, and negligible overhead cost.

We study a streaming network application-video transcoding to be executed on a multi-core server. It is important for the scheduler to minimize the total processing time and preserve good video quality in an energy-efficient manner. However, the performance of existing scheduling schemes is largely limited by ineffective use of the multi-core architecture characteristic and undifferentiated transcoding cost in terms of energy consumption. In this paper, we identify three key factors that collectively play important roles in affecting transcoding performance: memory access (M), core/cache topology (C) and transcoding format cost (C), or MC2for short. Based on MC2, we propose E-AHRW, an Energy-efficient Adaptive Highest Random Weight hash scheduler by extending the HRW scheduler proposed for packet scheduling on a homogeneous multiprocessor. E-AHRW achieves stream locality and load balancing at both stream and packet (frame) level by adaptively adjusting the hashing decision according to real-time weighted queue length of each processing unit (PU). Based on E-AHRW, we also design, implement and evaluate a hash-tree scheduler to further reduce the computation cost and achieve more effective load balancing on multi-core architectures. Through implementation on an Intel Xeon server and evaluations on realistic workload, we demonstrate that E-AHRW improves throughput, energy efficiency and video quality due to better load balancing, lower L2 cache miss rate and negligible scheduling overhead.

Traditional architectural designs are normally focused on CPUs and have been often decoupled from I/O considerations. They are inefficient for high-speed network processing with a bandwidth of 10Gbps and beyond. Long latency I/O interconnects on mainstream servers also substantially complicate the NIC designs. In this paper, we start with fine-grained driver and OS instrumentation to fully understand the network processing overhead over 10GbE on mainstream servers. We obtain several new findings: 1) besides data copy identified by previous works, the driver and buffer release are two unexpected major overheads (up to 54%); 2) the major source of the overheads is memory stalls and data relating to socket buffer (SKB) and page data structures are mainly responsible for the stalls; 3) prevailing platform optimizations like Direct Cache Access (DCA) are insufficient for addressing the network processing bottlenecks. Motivated by the studies, we propose a new server I/O architecture where DMA descriptor management is shifted from NICs to an on-chip network engine (NEngine), and descriptors are extended with information about data incurring memory stalls. NEngine relies on data lookups and preloads data to eliminate the stalls during network processing. Moreover, NEngine implements efficient packet movement inside caches to address the remaining issues in data copy. The new architecture allows DMA engine to have very fast access to descriptors and keeps packets in CPU caches instead of NIC buffers, significantly simplifying NICs. Experimental results demonstrate that the new server I/O architecture improves the network processing efficiency by 47% and web server throughput by 14%, while substantially reducing the NIC hardware complexity.

As the line speed of the network evolves at an unprecedented rate, a wide spectrum of network applications call for increasing processing density on network devices. The prevalence of multicore chips ameliorates the stress on processing power, but the QoS guarantee is often ignored. In addition, results of legacy QoS studies are difficult to apply to multicore web servers. Therefore, a multicore scheduler that incorporates QoS concerns is missing. As the network development moves towards cloud computing, we see an increasing importance of QoS guarantees on high performance multicore network appliances. In this paper, we propose a proportional share hash based scheduler, PS-HRW, which extends existing optimizations in multicore scheduling with QoS concerns. We address the network QoS requirement by assigning weights to each connection following the classic General Processor Sharing (GPS) theory. Based on our previous multicore scheduling studies, PS-HRW allocates computing resources based on the QoS requirement, such that the workload is balanced at the packet level, and the connection locality is maintained. To provide accurate QoS guarantee, PS-HRW allocates an integral number of cores first and then allocates the residuals using a partitioning theory. However, different from traditional simulation based approach, we target at two popular applications on modern network appliances: Deep Packet Inspection (DPI) and multimedia transcoding. In addition, we generalize the topology of different multicore architectures into a communication matrix and optimize PS-HRW to incorporate cache awareness. Essentially, PS-HRW schedules incoming traffic efficiently by balancing between connection locality, load balancing, core/cache topology and QoS guarantees.

We design, implement and evaluate a power-efficient and traffic-aware transcoding system on multicore servers that appropriately adjusts the processor operating level. The system is capable of configuring the number of active cores and core frequency "on-the-fly" according to the varying traffic rate. Results on an AMD machine show that our system saves 51.0% power consumption compared to a native system without power-saving schemes. It also outperforms three other power-aware systems, CG [2] (clock gating), C-DVFS [3] (chip-wide DVFS) and Hybrid [1] (chip-wide DVFS + power-gating), by 19.5%, 10.5% and 5.5% reduction of power consumption, respectively.

TCP/IP, the most commonly used network protocol, consumes a significant portion of time in Internet servers. While a wide spectrum of studies has been done to reduce its processing overhead such as TOE and Direct Cache Access, most of them did studies solely from the per-packet perspective and concentrated on the packet memory access overhead. They ignored per-session data TCP Control Block (TCB), which poses a challenge in web servers with a large volume of concurrent sessions.

Current packet processing systems only aim at producing high throughput without considering packet latency reduction. For many real-time embedded network applications, it is essential that the processing time not exceed a given threshold. In this paper, we propose LATA, a LAtency and Throughput-Aware packet processing system for multicore architectures. Based on parallel pipeline core topology, LATA can satisfy the latency constraint and produce high throughput by exploiting fine-grained task-level parallelism. We implement LATA on an Intel machine with two Quad-Core Xeon E5335 processors and compare it with four other systems (Parallel, Greedy, Random and Bipar) for six network applications. LATA exhibits an average of 36.5% reduction of latency and a maximum of 62.2% reduction of latency for URL over Random with comparable throughput performance.

IP lookup is in the critical data path in a high speed router. In this paper, we propose a new on-chip IP cache architecture for a high performance IP lookup. We design the IP cache along two important axes: cache indexing and cache replacement policies. First, we study various hash performance and employ 2-Universal hashing for our IP cache. Second, coupled with our cache indexing scheme, we present a progressive cache replacement policy by considering Internet traffic characteristics. Our experiments with IP traces show that our IP cache reduces the miss ratio by 15% and a small 32KB IP cache can achieve as high as 2Tbps routing throughput.

More complicated computational tasks are posed to the network equipments, such as Deep packet inspection (DPI) for network security check and network coding to achieve efficient multicast, etc. These complicated applications need processors to process the whole packet payload, potentially causing low throughput and long latency due to the large access delay to external memories. The behind hint lies that we can get the packet-processor/thread pair binding information in advance from the front-end dispatching component before the packet will be actually processed by cores. This interesting observation enables us design a new architecture of memory access for packet processors instead of the traditional model. In this paper we explore to apply push model to packet processors. The push model makes the data being pushed into the local memory/on-chip L1 cache in an on-demand and fine granularity manner ahead of being asked by running instructions, making a core always feels getting its data from the local memory/L1 cache instead of fetching them from the external memory in pull model. In order to verify the effectiveness, we design and implement the push model with the Intel IXP2850, and then conduct experiments to show the performance of push model in the IXP2850 simulator compared with the pull model. Simulation results indicate that applying push model to packet processors could improve the system throughput and reduce the packet processing latency and reducing required number of hardware threads.

A fundamental challenge of managing mutable data replication in a Peer-to-Peer (P2P) system is how to efficiently maintain consistency under various sharing patterns with heterogeneous resource capabilities. This paper presents a framework for balanced consistency maintenance (BCoM) in structured P2P systems. Replica nodes of each object are organized into a tree for disseminating updates, and a sliding window update protocol is developed to bound the consistency. The effect of window size in response to dynamic network conditions, workload updates and resource limits is analyzed through a queueing model. This enables us to balance availability, performance and consistency strictness for various application requirements. On top of the dissemination tree, two enhancements are proposed: a fast recovery scheme to strengthen the robustness against node and link failures; and a node migration policy to remove and prevent the bottleneck for better system performance. Simulations are conducted using P2PSim to evaluate BCoM in comparison to SCOPE. The experimental results demonstrate that BCoM significantly improves the availability of SCOPE by lowering the discard rate from almost 100% to 5% with slight increase in latency.

Current state-of-the-art task scheduling algorithms for network packet processing schedule the program into a parallel-pipeline topology on network processors to maximize the throughput. However, there has been no existing work targeting power budget for packet processing on off-the-shelf multicore architectures. As energy consumption, reliability and cooling cost for packet processing systems become increasingly important, it is necessary to integrate power-awareness into a scheduler to meet the power budget. In this paper, we propose a novel scheduling algorithm to optimize both throughput and latency given a power budget for network packet processing on multicore architectures. This algorithm addresses power-aware parallel-pipeline scheduling problem by applying per-core DVFS to optimally adjust frequency on each core. We implement our algorithm on an AMD machine with two Quad-Core Opteron 2350 processors and compare the results with existing algorithms given the same power budget. For six real packet processing applications, our algorithm improves throughput and reduces latency by an average of 64.6% and 25.2%, respectively.

Ubiquitous multi-core-based web servers and edge routers are increasingly popular in deploying computationally intensive Deep Packet Inspection (DPI) programs. Previous work has shown the benefits of connection locality-based scheduling on multi-core servers to improve L7-filter performance. However, we show that highly threaded hierarchical multi-core processors, such as the Sun Niagara 2 processor, accumulate imbalanced workload at each resource layer. This workload imbalance potentially offsets the benefits from connection locality. In addition, connection-locality-based load balance fails to work when network traffic is unevenly distributed.

This paper proposes a new server architecture EINIC (Enhanced Integrated NIC) for multi-core processors to tackle the mismatch between network speed and host computational capacity. Similar to prior work, EINIC integrates a redesigned NIC onto a CPU. However, we extend the integrated NIC (INIC) to multicore platforms and examine its behaviors with the network receiving optimization. Additionally, by exploiting NICs proximity to CPUs, we also design an I/O-aware last level shared cache (LLC). Our I/O-aware design allows us to split the cache into an I/O cache and a general cache in a flexible way. It ameliorates cache interferences between network and non-network data. Our simulation results show that EINIC not only attacks the mismatch, but also ameliorates the cache interference.

Several challenges in the IP lookup architecture must be addressed for a high-speed forwarding in a large scale routing table: power, memory, and lookup complexity. Hash-based architectures have lookup schemes that are recognized for being both power and memory efficient due to their O(1) lookup, in contrast to other contemporary architectures. In this paper, we propose a novel hash architecture to address these issues by using pipelined Bloom and fingerprint filters for a binary searching in keys. The proposed hash scheme encodes keys' indexes to an on-chip fingerprint table, approximately returns a few indexes in a key query without pointer overhead, and makes a perfect match in an off-chip key table. Due to a memory banking system in pipeline stages, we can achieve O(1) pipelined throughput complexity of insertion, deletion, and query operations. For the IP lookup, a Lulea bitmap with our hash scheme supports a prefix lookup without inflating the numbers of prefixes and next-hops, so that our scalable hash-based scheme can achieve the worst case O(1) IP lookup. The simulation with large scale routing tables shows that our IP lookup scheme offers 4.5 and 50.1 times memory and power efficiencies than other contemporary hash and TCAM schemes, respectively.

Distributed object search is the primary function of peer-to-peer (P2P) file sharing system to locate and transfer the file. The predominant search schemes in unstructured P2P systems have their problems: flooding creates excessive traffic overhead and random walk prolongs search delay. Moreover, both use uniform time-to-live (TTL) control for all users, which makes them vulnerable to selfish user attacks, and results in the "free-riding" and "tragedy of the commons" problems. In this paper, we propose a budget-based self-optimized incentive search (BuSIS) protocol for unstructured P2P file sharing systems, which is robust to and restricts selfish user behaviors. Furthermore, our protocol lowers the search overhead while keeping high hit rate. BuSIS provides differentiated search service for selfish users and ties a user's contribution to its service level. We present the analytical models on expected search performance, associated search cost and the user satisfaction level. Extensive emulations have been conducted at large scale network scenarios to compare performance of BuSIS with flooding and random walk searches with and without selfish user behaviors. The experimental results show that BuSIS always has the lowest search overhead without sacrificing the hit rate. When serving selfish users, flooding and random walk performance degrade dramatically, while BuSIS gracefully keeps the hit rate only with 20% overhead of flooding and 25% of random walk.

TPDS Editorial: EIC Farewell and New EIC Introduction

L7-filter is a significant component in Linux's QoS framework that classifies network traffic based on application layer data. It enables subsequent distribution of network resources in respect to the priority of applications. Considerable research has been reported to deploy multi-core architectures for computationally intensive applications. Unfortunately, the proliferation of multi-core architectures has not helped fast packet processing due to: 1) the lack of efficient parallelism in legacy network programs, and 2) the non-trivial configuration for scalable utilization on multi-core servers.In this paper, we propose a highly scalable parallelized L7-filter system architecture with affinity-based scheduling on a multi-core server. We start with an analytical study of the system architecture based on an offline design. Similar to Receive Side Scaling (RSS) in the NIC, we develop a model to explore the connection level parallelism in L7-filter and propose an affinity-based scheduler to optimize system scalability. Performance results show that our optimized L7-filter has superior scalability over the naive multithreaded version. It improves system performance by about 50% when all the cores are deployed.

Virtualization technology is now widely deployed on high performance networks such as 10-Gigabit Ethernet (10GE). It offers useful features like functional isolation, manageability and live migration. Unfortunately, the overhead of network I/O virtualization significantly degrades the performance of network-intensive applications. Two major factors of loss in I/O performance result from the extra driver domain to process I/O requests and the extra scheduler inside the virtual machine monitor (VMM) for scheduling domains.

Caching mechanism has achieved great success in general purpose processor; however, its deployment in Network Processor (NP) raises questions over its effectiveness under the new context. In this study, we thoroughly evaluate the performance of caches in NP with architectural features like multicore, multithread, and integrated packet interface. Our major findings include: (1) In general, a sufficiently large cache effectively reduces the number of memory requests and improves the utilization of the NP computation power. (2) The lower efficiency of private caches caused by duplicate information deteriorates the NP performance under certain circumstances. (3) The appropriate cache block size is constrained by the low spatial locality of network applications. (4) For workloads involving large amount of data movement, increasing cache size cannot bring more benefits when the bottleneck in interconnection bus is reached. In short, caching mechanism in NP can be helpful under appropriate usage.

Cisco Systems application oriented networking (AON) product is an important network element towards building next generation service oriented intelligent information network (IIN). AON processes application-level content and moves far beyond a conventional content-aware Web switch. It creates a novel content delivery platform and allows more sophisticated load balancing schemes to be deployed in a switch among back-end servers to reduce user-perceived response time. In this paper, we investigate different scheduling techniques for an AON system to maximize overall throughput and minimize latency per message for a heterogeneous server cluster consisting of different application servers. Based on a thorough evaluation of the three existing load balancing algorithms of AON, we propose a novel message type based service adaptive scheduling algorithm that makes AON more efficient and more intelligent. Systematic performance measurements, analyses, and comparisons are conducted to demonstrate the superiority of our intelligent message scheduling technique.

Cisco systems' application oriented networking (AON) is an important network element towards building next generation service oriented network. AON processes application- level content and moves far beyond a conventional content-aware Web switch. It creates a novel content delivery platform and allows more sophisticated message-level load balancing mechanisms to be deployed in a switch/router in front of back-end servers. In addition to the three existing load balancing algorithms of current AON system, round robin (RR), weighted round robin (WRR) and Adpative (ADP), we propose a new intelligent message-type-based adaptive scheduling algorithm that can maximize system performance with minimal user configuration complexity. We implemented this novel scheduler into AON system and conducted performance studies on all four scheduling schemes in terms of overall throughput, average latency, and server utilization. Experimental results show that our proposed scheduler outperforms the three existing schemes in all evaluation cases.

Efficiency and effectiveness are always the emphases of a scheduler, for both link and processor scheduling. Well-known scheduling algorithms such as surplus round robin (SRR) and elastic round robin (ERR) suffer from two fold shortcomings: 1) additional pre-processing queuing delay and post-processing resequencing delay are incurred due to the lack of short-term load-balancing; 2) bursty scheduling is caused due to blind preservation of scheduling history under non-backlogged traffic. In this paper, we propose a quantum-adaptive scheduling (QAS) algorithm, which: 1) synchronizes all the quanta in a fine-grained manner and, 2) adjusts the quanta intelligently based on processor utilization. We theoretically prove that the queuing fairness bound (QFB) for QAS is one third tighter than SRR and ERR. This result approaches the optimal value as obtained in shortest queue first (SQF) algorithm, while still maintaining O(1) complexity. Trace-driven simulations show that QAS reduces average packet delay by 18%~24% while cutting down the resequencing buffer size by more than 40% compared to SRR and ERR.

Spelling errors when typing a URL can be exploited by website-squatters: users are led to phony sites in a phenomenon we call parasitic URL naming. These phony sites imitate popular websites and try to extract personal information from unsuspecting users, or simply advertise and sell products to users. In this paper, we conduct a massive study in order to quantify the extent of this parasitic URL naming We start with a corpus of 900 popular websites, which we refer to as original URLs, and generate roughly 3 million URLs by varying the original names systematically and exhaustively. Over a period of 60 days, we analyze how many sites have URLs very similar to our original URLs. We find that parasitic URL naming is a wide-spread problem and quantify the extent of this issue. We believe that this work will provide the first step towards research and tools to combat web-fraud.

To share and exchange the files among Internet users, peer-to-peer (P2P) applications build another layer of overlay networks on top of the Internet infrastructure. In P2P file sharing systems, a file request takes two steps. First, a routing message is generated by the client (request initiator) and spread to the overlay network. After the process finishes, the location information of the requested file is returned to the client. In the second step, the client establishes direct connection(s) with the peer(s) who store a copy of that file to start the retrieving process. While numerous research projects have been conducted to design efficient, high-performance routing algorithms, few work concentrated on file retrieving performance. In this paper, we propose a novel and efficient algorithm - PROD to improve the file retrieving performance in DHT based overlay networks. In PROD, when a file or a portion of a file is transferred from a source peer to the client, instead of creating just one direct link between these two peers, we build an application level connection chain. Along the chain, multiple network links are established. Each intermediate peer on this chain uses a store-and-forward mechanism for the data transfer. PROD also introduces a novel topological based strategy to choose these peers and guarantees the transmission delay of each intermediate link is much lower than the direct link. We conducted extensive simulation experiments and the results shown that PROD can greatly reduce the transfer time per file in DHT base P2P systems.

Peer-to-Peer (P2P) networks have proven to be an efficient and successful mechanism for file sharing over the Internet. However, current P2P protocols have long worst case query latencies which prevents them from be employed for real time applications. Popularity of objects in these networks can change rapidly and augurs the need for a rapid and lightweight content replication strategy to reduce search and data-access latencies. In this paper, we propose an on-line pointer replication (OPR) algorithm in structured P2P networks which yields a significantly low worst case query latency. Also, the degree of replication achieved by OPR is dynamically adaptable to the instantaneous query arrival rate and churn characteristics of the system in order to reduce total control traffic. We evaluate and compare different replica placement strategies on the PlanetLab network as well as with simulations. Experimental results show that OPR outperforms the existing replica placement algorithms by at least 30% in average latency and around 40% in terms of maximum query latency.

With the advent of powerful network processors (NPs) in the market, many computation-intensive tasks such as routing table look-up, classification, IPSec, and multimedia transcoding can now be accomplished more easily in a router. An NP consists of a number of on-chip processors to carry out packet level parallel processing operations. Ensuring good load balancing among the processors increases throughput. However, such multiprocessing also gives rise to increased out-of-order departure of processed packets. In this paper, we first propose an Ordered Round Robin (ORR) scheme to schedule packets in a heterogeneous network processor assuming that the workload is perfectly divisible. The processed loads from the processors are ordered perfectly. We analyze the throughput and derive expressions for the batch size, scheduling time and maximum number of schedulable processors. To effectively schedule variable length packets in an NP, we propose a Packetized Ordered Round Robin (P-ORR) scheme by applying a combination of deficit round robin (DRR) and surplus round robin (SRR) schemes. We extend the algorithm to handle multiple flows based on a fair scheduling of flows depending on their reservations. Extensive sensitivity results are provided through analysis and simulation to show that the proposed algorithms satisfy both the load balancing and in-order requirements for parallel packet processing.

Deep Payload Inspection systems like SNORT and BRO utilize regular expression for their rules due to their high expressibility and compactness. The SNORT IDS system uses the PCRE Engine for regular expression matching on the payload. The software based PCRE Engine utilizes an NFA engine based on certain opcodes which are determined by the regular expression operators in a rule. Each rule in the SNORT ruleset is translated by PCRE compiler into an unique regular expression engine. Since the software based PCRE engine can match the payload with a single regular expression at a time, and needs to do so for multiple rules in the ruleset, the throughput of the SNORT IDS system dwindles as each packet is processed through a multitude of regular expressions.

Multi-Path Switching systems (MPS) are intensively used in the state-of-the-art core routers. One of the most intractable issues is how to load-balance traffic across its multiple paths while not disturbing the intra-flow packet orders. In this paper, based on the studies of tens of real Internet traces, we develop a novel scheme, namely Flow-Slice (FS), which cuts off each flow into flow-slices at every intra-flow interval larger than a slicing threshold set to 1ms 4ms and balances the load on the finer granularity. Through theoretical analyses and comprehensive trace-driven simulations, we show that FS achieves impressive load-balancing performance with little hardware cost while limiting the packet out-of-order chances to a negligible level (below 10 -6).

Mapping packet processing applications onto embedded network processors (NP) is a challenging task due to the unique constraints of NP systems and the characteristics of network application domains. A remarkable difference with general multiprocessor task scheduling is that NPs are often programmed into a hybrid parallel and pipeline topology.

Peer-to-Peer (P2P) systems provide decentralization, self-organization, scalability and failure-resilience, but suffer from high worst-case latencies. Researchers have proposed various replication algorithms to place multiple copies of objects across the network in pursuit of better performance for P2P computing; nevertheless, they neither presented clear analysis nor derived worst-case bound for their algorithms. In this paper, we model the replica placement problem arising in real-world P2P networks as a Clustered K-Center problem which we prove to be NP-complete. Then we propose an efficient approximation algorithm to this problem with a provable upper bound. Extensive experiments have been conducted to demonstrate the effectiveness and efficiency of our algorithm. The experimental results show that our approach can run several orders of magnitude faster than the optimal solution while being able to minimizing the query latency.

We consider fair allocation of sessions at the outputs of optical cross-connects employing wavelength division multiplexing (WDM). Each session consists of traffic on one or more wavelengths (channels). We identify lexicographic fairness as the most appropriate fairness criterion that is relevant to this setting. Achieving a fair lexicographic solution, commonly referred to as lexicographic optimality (LEX), is trivial and polynomial-time computable when any incoming wavelength can be converted to any outgoing wavelength (full conversion). This is not apparent in the practical and realistic case of limited conversion. We prove that LEX is also polynomial-time computable for the limited conversion case by reducing the problem to a min-cost max-flow optimization objective in network flows. We also motivate, formulate and solve a stronger variant of lexicographic optimality that we refer to as worst-case fair lexicographic optimal (W-LEX). Although our effective setting is an optimization problem in bipartite graphs (the request graph is bipartite), the network-flow based algorithms are applicable to unit capacity graphs in general. Further, we provide fast polynomial-time algorithms that furnish solutions for LEX and the W-LEX optimality problems for arbitrary bipartite graphs (i.e. arbitrary wavelength-conversion rules) and are computationally less expensive than network-flow methods. Finally we report simulation results to validate our findings.

A good crossbar switch scheduler should be able to sustain full bandwidth and maintain fairness among competing flows. A pure input-queued (IQ) non-buffered switch requires an impractically complex scheduler to achieve this goal. Common solutions are to use crossbar speedup and/or buffered crossbar. In this paper, we explore this issue in a buffered crossbar without speedup. We first discuss the conflict between fairness and throughput and the fairness criteria in crossbar switch scheduling, and justify that a desirable scheduler should sustain full bandwidth for admissible traffic and ensure max-min fairness for non-admissible traffic. Then we describe anadaptive max-min fair scheduling(AMFS) algorithm and show by analysis and simulation that it can provide both 100% throughput and max-min fairness. Finally we briefly discuss the hardware implementation of the AMFS algorithm.

In this paper, we propose a novel and efficient content-aware dispatching algorithm. Our approach eliminates the potential bottleneck and the single point of failure problems completely by using totally decentralized P2P architecture. It is scalable, the system throughput increases nearly linearly with the increased number of servers. Meanwhile, it does not introduce heavy communication overhead among back-end servers which appeared in the previous decentralized mechanisms. Our simulation results show that our approach is superior to the previous solutions.

Network processors (NPs) have emerged as successful platforms for providing both high performance and flexibility in building powerful routers. Typical NPs incorporate multiprocessing and multithreading to achieve maximum parallel processing capabilities. We observed that under low incoming traffic rates, processing elements (PEs) in an NP are idle for most of the time but still consume dynamic power. This paper develops a low-power technique to reduce the activities of PEs in accordance with the varying traffic volume. We propose to monitor the average number of idle threads in a time window, and gate off the clock signals to unnecessary PEs when a subset of PEs is enough to handle the network traffic. We solve the difficulties arising from clock gating the PEs, such as redirecting network packets, determining the thresholds of turning on/off PEs, and avoiding unnecessary packet loss. Our technique brings significant reduction in power consumption of NPs with no packet loss and little impact on overall throughput.

Data movement (memory copies) is a very common operation during network processing and application execution on servers. The performance of this operation is rather poor on today's microprocessors due to the following aspects: 1) Several long-latency memory accesses are involved because the source and/or the destination are typically in memory, 2) latency hiding techniques, such as out-of-order execution, hardware threading, and prefetching, are not very effective for bulk data movement, and 3) microprocessors move data at register (small) granularity. In this paper, we show this overhead of bulk data movement and propose the use of dedicated copy engines to minimize it. We present a detailed analysis of copy engine architectures along two dimensions: 1) on-die versus off-die and 2) synchronous versus asynchronous. These copy engine architectures are superior to traditional direct memory access (DMA) engines because they are tightly coupled to the core architecture and enable lower overhead communication and signaling. We describe the hardware support required to implement these copy engines and integrate them into server platforms. We perform a detailed case study to evaluate the performance of these copy engines. The evaluation is based on an execution-driven simulator, which was extended with detailed models of copy engines. Our simulation results show that copy engines are effective in reducing the bulk data movement overhead and, hence, hold significant promise for high-performance server platforms

In DHT based P2P systems, various issues such as peer heterogeneity, network topology, and diverse file popularity, may affect the DHT system efficiency. In this paper, we propose an effective load balancing algorithm for DHT-Based P2P systems. Our main contributions are: (1) we propose an fully distributed mechanism to maintain the history of file access information. This information is used to predict the future file access frequencies and support the load distribution and redistribution operations; (2) we design a novel load balancing algorithm, which takes the file access history and peer heterogeneity properties into account to determine the load distribution. Our algorithm can generate the best load distribution decision when a new peer comes, it can also be able to dynamically perform the load redistribution during system running time if overloaded peers appeared. In our algorithm, no virtual servers are used, thus we have less processing overhead on the expensive routing metadata maintenance; (3) finally, we design a topologically-aware data replication mechanism, the topological information of the peers are used for file replication decisions. A file is replicated only on a peer close to the group of peers which have high access frequencies.

Content delivery network (CDN) plays an important role in today's Web services. More and more content providers use CDNs to lower the server overhead, reduce client perceived latency and decrease network traffic. More research papers have been published in recent years addressing CDN system performance issues. However, most of them are concentrated on server placement policy, content distribution mechanism and request routing algorithm. In this paper, we propose a new CDN architecture to improve system performance by grouping the content servers which are topologically close into server clusters and exploiting the benefits of server cooperation. In our approach, when a server receives a request and cannot fulfil this request, it will forward the request to other nearby servers in this cluster. If there is a cache bit, the data can be fetched immediately. Only in case none of the servers can satisfy this request, the data will be fetched from the original server. Furthermore, with the server coordination, system workload can be well balanced on several servers. We conduct extensive simulations and the results show that our solution achieves significant improvement over the conventional CDN architecture

We address the quality of service (QoS) provisioning problem in an aggregated multi-server environment. The input packet stream traffic to the system is categorized at a macro level into a few "flow-classes" that require service differentiation; each class is further subdivided into "flows" at the micro-level. Flows can be serviced by any server: however; the service rate is a function of the class and the particular server. Given such an environment, we have a multi-criteria optimization objective: (i) provide differentiated service to flows, (ii) achieve load balancing of the servers and (iii) maximize their throughput (amount of bytes serviced). We present an on-line fluid-based approximation scheme to schedule packets. Modeling the accumulated traffic in a class as fluid we use linear programming to first determine the optimal fractions that should be directed to different servers while ensuring fairness and high server throughput. We propose a packet scheduling strategy for the multi-server framework (by extending a well-known fair round-robin algorithm for single link systems) that effectively incorporates the optimal service fractions determined in the previous step. We validate the proposed algorithm with extensive simulations. The results show that the algorithm imparts high throughput with good service differentiation. We also evaluate reordering of packet requests within flow streams by presenting relevant metrics that quantify reordering

In this paper, we present a distributed computing framework designed to support higher quality of service and fault tolerance for processing deadline-driven tasks in a P2P environment. Our proposed strategy strives to build an open infrastructure that is accessible by ordinary users for both cycle donation and consumption. For jobs that fail to be locally accommodated, the proposed scheduler MET (maximum efficiency tree) builds a dynamic multi-level resource tree with minimal yet sufficient power to process the job prior to its deadline. The peer selection policy is based on a joint evaluation of the computational power and communication bandwidth at the nodes. Further, with an optimal load sharing scheme, the resulting resource tree is guaranteed to be power efficient. The proposed computing protocol offers an approach for utilizing idle computing cycles of peer computers on the Internet in a P2P manner. The protocol exhibits three attractive features - decentralized operation, optimized load balancing and guaranteed resource utilization. Extensive simulation experiments are conducted to study the effectiveness of the proposed framework under various network conditions. We compare our strategy with two other tree construction algorithms, namely MST (minimum spanning tree) and MCT (maximum computation tree). It is demonstrated that MET outperforms both MST and MCT consistently. Further, sensitivity results with random node failure/join are also furnished

1045-9219/06/$20.00 © 2006 IEEE Published by the IEEE Computer Society For information on obtaining reprints of this article, please send e-mail to: [email protected]. I T is a great privilege and honor to serve as the Editor-in-Chief (EIC) of the IEEE Transactions on Parallel and Distributed Systems (TPDS). TPDS is a relatively young journal that started in 1990, yet it has become the premier outlet for research publications in the parallel and distributed processing area. The credit for this accomplishment goes to all the four previous EICs, associate editors, reviewers, and the authors who submitted their papers to TPDS for publication. Currently, the first review turn around time for a submission is below six months, meaning that a paper can get accepted for TPDS as fast as a conference. At the same time, a paper submitted to TPDS can go through minor or major revision and, finally, get accepted, which is not possible in conferences. The timely review and publication of papers in TPDS is now possible because of the combined effort of the last EIC, Pen-Chung Yew, and his staff. While I am assuming the EIC job in a very comfortable position with regard to visibility and publication timing, there are a few challenges that need our urgent attention. TPDS was born while research in the area of parallel processing was at its peak. Also, the competition with other journals and conferences was not that fierce. Now, we need to take a closer look at the scope of TPDS and revise it to include emerging areas, technological advancements, and experimental results in the systems area to boost the number of submissions. I shall invite well-recognized researchers to organize special issues and appoint some of them to the editorial board. I also plan to appoint an associate Editor-in-Chief to help me in various areas. In order to reduce the delay in publication further, I would urge the associate editors to administratively reject submissions if the research is outdated, and cut down on major revisions, recommending some of them for new submission after revision. I would urge understanding on the part of authors if they are advised to do so. I would also request the associate editors to review some papers themselves instead of waiting for the reviewer’s response indefinitely. The TPDS staff will closely monitor the review time of a paper and bring it to our attention if such an action is needed. An IEEE Transactions cannot gain a good reputation without the active support and participation of the research community in the area. I invite you to send me your suggestions to further enhance the quality and visibility of the TPDS. I look forward to working with you during the next two years to take TPDS to the next level of excellence.

We consider a cluster-based multimedia Web server that dynamically generates video units to satisfy the bit rate and bandwidth requirements of a variety of clients. The media server partitions the job into several tasks and schedules them on the backend computing nodes for processing. For stream-based applications, the main design criteria of the scheduling are to minimize the total processing time and maintain the order of media units for each outgoing stream. In this paper, we first design, implement, and evaluate three scheduling algorithms, First Fit (FF), Stream-based Mapping (SM), and Adaptive Load Sharing (ALS), for multimedia transcoding in a cluster environment. We determined that it is necessary to predict the CPU load for each multimedia task and schedule them accordingly due to the variability of the individual jobs/tasks. We, therefore, propose an online prediction algorithm that can dynamically predict the processing time per individual task (media unit). We then propose two new load scheduling algorithms, namely, Prediction-based Least Load First (P-LLF) and Prediction-based Adaptive Partitioning (P-AP), which can use prediction to improve the performance. The performance of the system is evaluated in terms of system throughput, out-of-order rate of outgoing media streams, and load balancing overhead through real measurements using a cluster of computers. The performance of the new load balancing algorithms is compared with all other load balancing schemes to show that P-AP greatly reduces the delay jitter and achieves high throughput for a variety of workloads in a heterogeneous cluster. It strikes a good balance between the throughput and output order of the processed media units.

TCP Splicing can be used in content-aware switches to tremendously reduce overall request latency. In order to reduce the processing latency further, we propose to offload the protocol processing onto network processors (NPs). An NP consists of a multithreaded multiprocessor architecture that can provide high throughput for packet processing or forwarding. However, offloading any protocol software to an NP needs to be carefully designed due to its low-level programming and limited control memory size.In this paper, we first analyze the operation of TCP Splicing in detail and evaluate its performance through measurements on a Linux-based switch. Then various possibilities of workload allocation among different computation resources in an NP are presented, and the design tradeoffs are discussed. A content aware switch is implemented using IXP 2400 NP and evaluated for performance comparison. The measurement results demonstrate that our NP-based switch can reduce the http processing latency by an average of 83.3% for a 1K byte web page. The amount of reduction increases with larger file sizes. It is also shown that the packet throughput can be improved by up to 5.7x across a range of files by taking advantage of multithreading and multiprocessing, available in the NP.

Network processors (NPs) have emerged as successful platforms to providing both high performance and flexibility in building powerful routers. Typical NPs incorporate multiprocessing and multi-threading to achieve maximum parallel processing capabilities. We observed that under low incoming traffic rates, most processing elements (PEs) in NPs are nearly idle and yet still consume dynamic power. This paper develops a low power technique to reduce the activities of PEs according to the varying traffic volume. We propose to monitor the average number of idle threads in a time window, and gate off the clock network of unused PEs when a subset of PEs is enough to handle the network traffic. We show that our technique brings significant reduction in power consumption (up to 30%) of NPs with no packet loss and little impact to the overall throughput.

A smooth scheduling with guaranteed rate service and bounded packet delay is a desired objective of any switch scheduling algorithm. We present a scheme that generates low jitter schedules with low computational complexity. The scheduler uses an integer decomposition of the rate-matrix, similar to the Birkhoff-von Neumann decomposition. It improves the delay and jitter performance of the smooth scheduler as described in Keslassy et al. with an increase in the number of permutation matrices that the switch fabric has to cycle through. This increase is shown to be a constant for all practical purposes. Two algorithms are presented that have time complexity O(n/sup 2/ + log n) and space complexity O(n/sup 2/) and O(n) respectively. An existing scheduling algorithm for single links, smoothed round robin, is employed for scheduling the permutation matrices. This algorithm has a computational complexity overhead of O(1) and ensures smooth scheduling.

Recently, content distribution networks (CDNs) have attracted a great deal of attention from both the industry and academic communities. We design efficient object replication algorithms to achieve the optimal performance while not violating clients' QoS requirements in CDN. We use a three-stage mechanism: first, object replication constraints to meet the QoS requirements are generated; second, a minimal object replication set (MORS), which can satisfy the constraints with the minimal number of replicas on each server, is created; and finally, more objects are replicated on the servers with spare space to further improve the performance. We propose a number of heuristic algorithms and conduct trace-driven experiments to evaluate the performance

In this paper, we propose a distributed packet processing algorithm on a peer-to-peer (P2P) network with the objective to minimize the total processing time. We consider an arbitrary P2P network comprising heterogeneous nodes interconnected via heterogeneous links. Each node on the network has its own local workload to be processed and is ready to share its extra processing power among other peer nodes upon request. We distribute the workload of a host to its peers by organizing them into an efficient resource tree. Since the key idea of this algorithm is to effectively share the available resources on the network by processing the load in a distributed manner, we refer to this approach as resource sharing distributed load processing (RSDLP) algorithm. We evaluate the performance with rigorous simulation experiments under generic system parameters.

In this paper, we propose a novel strategy to determine the optimal network processor (NP) topology for the target application tasks. We partition network applications into different stages with the consideration of limited instruction memory of the processing elements (PEs). We develop a theoretical approach to determine an optimal topology of the PEs via multiple pipelines. The idea of multiple pipelining is to exploit the task/packet level parallelism and the pipelines are further optimized to achieve the maximum throughput and resource utilization. Simulation results verify our analytical model and demonstrate the robustness of our approach in different NP configurations.

Fairness and high throughput are two desirable properties for scheduling best-effort traffic in an input-queued crossbar switch. Unfortunately, to the best of our knowledge, existing scheduling schemes cannot achieve both goals. In this paper, we discuss the conflict between fairness and throughput and the fairness criterion in the context of an input-queued crossbar switch, and justify that a desirable scheduler should sustain full bandwidth for admissible traffic and ensure max-min fairness for non-admissible traffic. To this purpose, we propose an algorithm called largest virtual waiting time first (LVWTF).

Provisioning quality of service (QoS) across an aggregate of transmission entities (e.g., link aggregation) or processing elements (e.g. network processors) is a challenging problem. The difficulty lies in simultaneously satisfying fairness to flows (with different bandwidth requirements) and ensuring minimized intra-flow reordering. This problem is crucial to many applications (that utilize parallel communication or processing paths) like multi-path load distribution, multi-path storage I/O, web service, data processing by network processors in the datapath of routers, transcoding multimedia flow traffic content over the Internet to name a few. We present two algorithms for multi-link systems that aim at reducing undesired reordering, ensure fair sharing of flows and optimal utilization of the links. Our algorithms are based on a new approach of dynamically partitioning flows among links. We perform simulations on real Internet traces to validate our algorithmic approach.

Bulk data movement occurs commonly in server work-loads and their performance is rather poor on today's microprocessors. We propose the use of small dedicated copy engines, and present a detailed analysis of a bulk data copy engine architecture. We describe the hardware support required to implement the copy engine and to tightly integrate it into server platforms. Our evaluation is based on an execution driven simulator that was extended with detailed models of bulk data movement engines. The simulation results show that dedicated engines are quite effective in eliminating the data movement overhead and are an attractive choice for handling bulk data in future high performance server platforms.

Several companies have introduced powerful network processors (NPs) that can be placed in routers to execute various tasks in the network. These tasks can range from IP level table lookup algorithm to application level multimedia transcoding applications. An NP consists of a number of on-chip processors to carry out packet level parallel processing operations. Ensuring good load balancing among the processors increases throughput. However, such multiprocessing also gives rise to increased out-of-order departure of processed packets. In this paper, we first propose a dynamic batch co-scheduling (DBCS) scheme to schedule packets in a heterogeneous network processor assuming that the workload is perfectly divisible. The processed loads from the processors are ordered perfectly. We analyze the throughput and derive expressions for the batch size, scheduling time and maximum number of schedulable processors. To effectively schedule variable length packets in an NP, we propose a packetized dynamic batch-coscheduling (P-DBCS) scheme by applying a combination of deficit round robin (DRR) and surplus round robin (SRR) schemes. We extend the algorithm to handle multiple flows based on a fair scheduling of flows depending on their reservations. Extensive sensitivity results are provided through analysis and simulation to show that the proposed algorithms satisfy both the load balancing and in-order requirements in packet processing.

In peer-to-peer (P2P) file sharing systems, the participating peers share the files with others. Two steps are needed for file sharing: first, a routing request is generated and sent to other peers by using a routing algorithm. The feedback received by the client contains the location information of the requested files; second, the client retrieves the file from one or more peers which have a copy of that file. Routing algorithms have great impact on the overall system performance, distributed hash table (DHT) based routing algorithms provide an elegant and efficient mechanism and become popular in recent years. However, two problems exist in DHT algorithms. First, to find out the location information, in some cases, the routing request may traverse distant peers around the world; second, in case of multiple copies of the requested file stored on different peers, there's no way to figure out which peer is the topologically closest to the client. Thus, the client may have to download the file from a remote peer and suffer from long retrieve latency. In this paper, we propose a hierarchical routing and retrieving algorithm to relieve these problems. The peers' topological information is utilized. Our algorithm is able to find out the closest copy for any routing requests. The simulation results show our strategy can significantly improve the system routing and retrieval performance.

A wide spectrum of e-commerce (B2B/B2C), banking, financial trading and other business applications require the exchange of data to be highly secure. The Secure Sockets Layer (SSL) protocol provides the essential ingredients of secure communications - privacy, integrity and authentication. Though it is well-understood that security always comes at the cost of performance, these costs depend on the cryptographic algorithms. In this paper, we present a detailed description of the anatomy of a secure session. We analyze the time spent on the various cryptographic operations (symmetric, asymmetric and hashing) during the session negotiation and data transfer. We then analyze the most frequently used cryptographic algorithms (RSA, AES, DES, 3DES, RC4, MD5 and SHA-1). We determine the key components of these algorithms (setting up key schedules, encryption rounds, substitutions, permutations, etc) and determine where most of the time is spent. We also provide an architectural analysis of these algorithms, show the frequently executed instructions and discuss the ISA/hardware support that may be beneficial to improving SSL performance. We believe that the performance data presented in this paper is useful to performance analysts and processor architects to help accelerate SSL performance in future processors

Ternary content addressable memories (TCAMs) have been emerging as a popular device in designing routers for packet forwarding and classifications. Despite their premise on high-throughput, large TCAM arrays are prohibitive due to their excessive power consumption and lack of scalable design schemes. We present a TCAM-based router architecture that is energy and storage efficient. We introduce prefix aggregation and expansion techniques to compact the effective TCAM size in a router. Pipelined and paging schemes are employed in the architecture to activate a limited number of entries in the TCAM array during an IP lookup. The new architecture provides low power, fast incremental updating, and fast table look-up. Heuristic algorithms for page filling, fast prefix update, and memory management are also provided. Results have been illustrated with two large routers (bbnplanet and attcanada) to demonstrate the effectiveness of our approach.

System level modeling with executable languages such as C/C++ has been crucial in the development of large electronic systems from general processors to application specific designs. To make sure that the executable models behave as they should, the designers often have to "eye-ball" the simulation traces and at best, apply simple "assert" statements or write simple trace checkers in some scripting languages. The problem is the lack of a concise and formal method to specify and check desired properties, whether they be functional or performance in nature. In this paper, we apply assertion checking methodology to the system design of network processors. Functional and performance assertions, based on linear temporal logic and logic of constraints, are written during the design process. Trace checkers and simulation monitors are automatically generated to validate particular simulation runs or to analyze their performance characteristics. Several categories of assertions are checked throughout the design process, such as equivalence, functionality, transaction, and performance. We demonstrate that the assertion-based methodology is very useful for both system level verification and design exploration.

Several companies have introduced powerful network processors (NP) that can be placed in active routers to execute application level tasks in the network. An NP consists of a number of on-chip processors to carry out packet level parallel processing operations. We propose to employ them for multimedia streaming (transcoding) to convert the incoming video streams to low bit-rate media units as per the requirements of the clients. To effectively schedule the parallel transcoding operations in an active router, we propose a static sequentialized batch-coscheduling (SSBC) scheme to meet both load balancing and real-time requirements for media streaming, based on divisible load theory (DLT). We first analyze the feasibility and optimality of the load distribution schemes from the theoretical perspectives, and then present separate solutions for non-delay-sensitive streams and delay-sensitive streams. Rigorous simulations and experiments have been carried out to evaluate the performance.

With today's ASIC technology, a large amount of memory can be easily implemented in a single chip. This makes the combined input-crosspoint-queued (CICQ) crossbar switch a more attractive solution than the traditional input-queued (IQ) crossbar switch because of the simplicity of the CICQ switch scheduling. We propose a shortest crosspoint buffer first (SCBF) scheme, and prove that it achieves 100% throughput for any admissible traffic. To facilitate hardware implementation, a maximal SCBF solution is also proposed. Our simulations show that the maximal SCBF performs almost identically to the maximum solution, and better than existing IQ and CICQ schemes. The time complexity of the maximal SCBF is O(log N), feasible for fast hardware implementation.

Summary form only given. Web caching is the most important technique to reduce network bandwidth consumption and minimize user-perceived latency. However, most researches are focused on designing efficient architectures with dedicated proxy servers, the potential advantage of utilizing client cache is not fully exploited. We propose a new solution to improve Web caching performance using local cache on client computers. Our system has several advantages than the dedicated proxy server mechanism. First, a larger virtual cache is generated to cache more documents than a single proxy server. Second, it is scalable, system workloads are distributed all across client computers instead of concentrated on a central server, the "hot spot" and "single point of failure " problems are relieved. Third, by the introduction of the superclients, the effect of the weak clients in a fully decentralized scheme is also alleviated. The simulation results show our system can achieve better system caching performance and scalability than the previous solutions.

Summary form only given. Well-organized proxy caching systems can greatly reduce the user perceived latency and decrease the network bandwidth consumption. In this paper, we propose a new hash based Web caching architecture, Tulip. Tulip extends the locality-based algorithm in UCFS as the basic data grouping scheme in hash based proxy systems, uses it to aggregate Web objects which are likely to be accessed together into object clusters and uses these clusters as the primary access units between memory and disk. The overhead of slow disk I/Os is greatly reduced. It also presents a simple and efficient data duplication scheme. Along with the local caching strategy, Tulip can achieve both fault tolerance and load balance with minimal overhead introduced. Our simulation results show Tulip is scalable and robust, it has better performance than previous approaches.

Reducing the power consumption of computing devices has gained a lot of attention recently. Many research works have focused on reducing power consumption in the off-chip buses as they consume a significant amount of total power. Since the bus power consumption is proportional to the switching activity, reducing the bus switching is an effective way to reduce bus power. While numerous techniques exist for reducing bus power in address buses, only a handful of techniques have been proposed for data-bus power reduction, where Frequent Value Encoding (FVE) is the best existing scheme to reduce the transition activity on the data buses.In this paper, we propose improved frequent value data-bus encoding techniques aimed at reducing more switching activity and hence, more power consumption. We propose three new schemes and five new variations to exploit bit-wise temporal and spatial locality in the data bus values. Our technique does not use additional external control signal and captures bit-wise locality to efficiently encode data values. For all the embedded and SPEC applications we tested, the overall average switching reduction is 53% over unencoded data and 11% more than the conventional FVE scheme.

We address the problem of fair scheduling of packets in Internet routers with input-queued switches. The goal is to ensure that packets of different flows leave a router in proportion to their reservations under heavy traffic. First, we examine the problem when fair queuing is applied only at output link of a router, and verify that this approach is ineffective. Second, we propose a flow-based iterative deficit-round-robin (iDRR) fair scheduling algorithm for the crossbar switch that supports fair bandwidth distribution among flows, and achieves asymptotically 100% throughput under uniform traffic. Since the flow-based algorithm is hard to implement in hardware, we finally propose a port-based version of iDRR (called iPDRR) and describe its hardware implementation.

A remote memory access poses a severe problem for the design of CC-NUMA multiprocessors because it takes an order of magnitude longer than the local memory access. The large latency arises partly due to the increased distance between the processor and remote memory over the interconnection network. In this paper, we develop a new switch architecture, called Switch MSHR (SMSHR), which provides the cache block to the requesting processors without those requests having to go to the home memory. The SMSHR idea is based on providing a few miss status holding registers (MSHRs) in each switch that keep track of read requests to the memory. The SMSHR blocks secondary requests to the same memory block and provides them with a copy of the block when the primary reply returns. The SMSHR design is then extended to include a switch cache, which can temporarily save a copy of the data block for later use. We provide basic block designs for the SMSHR and SIVISHR+cache architectures in this paper. We explore the design space by modeling the new switch architectures in a detailed execution-driven simulator and analyze the performance benefits. Our Simulation results show that applications with a high degree of data sharing benefit tremendously from the SMSHR and SMSHR+cache techniques.

We propose new shared memory multiprocessor architectures and evaluate their performance for future Internet protocol (IP) routers based on symmetric multiprocessor (SMP) and cache coherent nonuniform memory access (CC-NUMA) paradigms. We also propose a benchmark application suite, RouterBench, which consists of four categories of applications representing key functions on the time-critical path of packet processing in routers. An execution driven simulation environment is created to evaluate SMP and CC-NUMA router architectures using this RouterBench. The execution driven simulation can produce accurate cycle-level execution time prediction and reveal the impact of various architectural parameters on the performance of routers. We port the FUNET trace and its routing table for use in our experiments. We find that the CC-NUMA architecture provides an excellent scalability for design of high-performance IP routers. Results also show that the CC-NUMA architecture can sustain good lookup performance, even at a high frequency of route updates.

Input buffered switch architecture has become attractive for implementing high performance routers, and expanding use of the Internet sees an increasing need for quality of service. It is challenging to provide a scheduling technique that is both highly efficient and fair in resource allocation. We first introduce an iterative fair scheduling (iFS) scheme for input buffered switches that supports fair bandwidth distribution among the flows and achieves asymptotically 100% throughput. The iFS is evaluated both under synthetic workload and with Web traces from the Internet. Compared to the commonly used synthetic input, our simulation results reveal significant difference in performance when real network traffic is employed. We then consider fair scheduling under various buffer management mechanisms and analyze their impact on the fairness in bandwidth allocation. Our studies indicate that early packet discard in anticipation of congestion is necessary and per-flow based buffering is effective for protecting benign users from being adversely affected by misbehaved traffic. Buffer allocation according to bandwidth reservation is especially helpful when the input traffic is highly bursty.

Input buffered switch architecture has become attractive for implementing high performance routers and expanding use of the Internet sees an increasing need for quality of service. It is challenging to provide a scheduling technique that is both highly efficient and fair in resource allocation. In this paper, we first introduce an iterative fair scheduling (IFS) scheme for input buffered switches that supports fair bandwidth distribution among the flows and achieves asymptotically 100 percent throughput. The IFS is evaluated both under synthetic workload and with Web traces from the Internet. Compared to the commonly used synthetic input, our simulation results reveal significant difference in performance when the real network traffic is employed. We then consider fair scheduling under various buffer management mechanisms and analyze their impact on the fairness in bandwidth allocation. Our studies indicate that early packet discard in anticipation of congestion is necessary and per-flow based buffering is effective for protecting benign users from being adversely affected by misbehaving traffic. Buffer allocation according to bandwidth reservation is especially helpful when the input traffic is highly bursty.

Input buffered switch architecture has become attractive for implementing high performance switches for workstation clusters. It is challenging to provide a scheduling technique that is both highly efficient and fair in resource allocation. In this paper, we first introduce an iterative fair scheduling(iFS) scheme for input buffered switches that supports fair bandwidth distribution among the flows and achieves asymptotically 100% throughput. We then apply the idea of fair scheduling to switches with multicasting capability and propose an mFS scheme which allocates bandwidth to various flows according to their reservations. We show that mFS produces throughput comparable to the existing schemes while distributing the bandwidth as per the given reservations. Extensive simulation results are presented to validate the effectiveness of our proposed schemes.

A number of approaches have been proposed by different vendors for the next generation Internet router architectures, capable of processing millions of packets per second. Most of this processing speed stems from employing latest high-performance network processor or multiprocessors as the forwarding engine of the router However, all these improvements have been proposed without any detailed study in performance evaluation. The impact of instruction level parallelism, branch prediction, multiprocessing, and cache architectures on the performance of routers is not known. In the paper a methodology is proposed, which extends an execution-driven simulator to evaluate router architectures. We incorporate the exact model of an IP router into RSIM to analyze its performance and also develop a framework for feeding real Internet traces to the simulator Our work enables us to vary system parameters to simulate and analyze designs of realistic system with a range of traces. It is shown that the performance of Internet routers can be dramatically enhanced by using multiprocessor architectures. The router design also considers various cache replacement policies and router arbitration policies.

In this paper a wave-pipelining scheme is used to increase the performance of a router architecture. Wave-pipelining has a potential of significantly reducing clock cycle time and power. The design approach considered in this paper allows the propagation of data from stage to stage to occur without the use of intermediate latches. Control signals are used to ensure that intermixing of data waves does not occur. The results of the study show that wave-pipelining helps to reduce the clock period.

When proposing new architectural enhancements, it is also important to account for the hardware complexity. To achieve this goal, we propose to model the new design in a hardware description language (HDL), synthesize the HDL code, and infer a realistic clock cycle which will be used in subsequent simulations. For accurate results, we develop a two-level hierarchical simulation technique, where an execution driven simulator (RSIM) and an HDL simulator (Verilog-XL) are coupled together to evaluate an entire system. We detail the simulation process and show its impact on the design of an interconnect switch architecture for CC-NUMA multiprocessors.

Applications with widely shared data do not perform well on cc-NUMA multiprocessors due to the hot-spots they create in the system. In this paper we address this problem by enhancing the memory controller with a forwarding mechanism capable of hiding the read latency of widely shared data, while potentially decreasing the memory and network contention. Based on the influx of requests, the memory anticipates the next read references and forwards the data in advance to the processors. To identify the set of processors the data is to be forwarded to we use a heuristic based on the spatial locality of memory blocks. To increase the forwarding effectiveness and minimize the number of messages, we incorporate simple filters combined with a feedback mechanism. We also show that further improvements are possible using a combined software-prefetching/hardware-forwarding approach. Our experimental results obtained with a detailed execution driven simulator with ILP processors show significant improvements in execution time (up to 37%).

In this paper we propose a novel hardware caching technique, called switch directory, to reduce the communication latency in CC-NUMA multiprocessors. The main idea is to implement small fast directory caches in crossbar switches of the inter-connect medium to capture and store ownership information as the data flows from the memory module to the requesting processor. Using the stored information, the switch directory re-routes subsequent requests to dirty blocks directly to the owner cache, thus reducing the latency for home node processing such as slow DRAM directory access and coherence controller occupancies. The design and implementation details of a DiRectory Embedded Switch ARchitecture; DRESAR, are presented. We explore the performance benefits of switch directories by modeling DRESAR in a detailed execution driven simulator. Our results show that the switch directories can improve performance by up to 60% reduction in home node cache-to-cache transfers for several scientific applications and commercial workloads.

The switch design for interconnection networks plays an important role in the overall performance of multiprocessors and computer networks. It is therefore crucial to study various factors in the switch design space and their influence on the system performance. In this paper we first propose a 4-D framework for the design of input queuing switches with wormhole routing and virtual channels. Then we explore the design space to examine in detail the impact of four parameters: virtual channel allocation, intraswitch connectivity buffer space allocation and link arbitration policy. Our simulations, performed with an execution driven simulator with ILP processors, show that the cumulative effect of the four switch enhancements ranges between 7% and 38%. The most important parameter proves to be VC allocation method (up to 28% improvements in execution time). The other three bring about the same level of performance: between 1% and 7% depending on the application.

Cache coherent nonuniform memory access (CC-NUMA) multiprocessors provide a scalable design for shared memory. But, they continue to suffer from large remote memory access latencies due to comparatively slow memory technology and large data transfer latencies in the interconnection network. In this paper, we propose a novel hardware caching technique, called switch cache, to improve the remote memory access performance of CC-NUMA multiprocessors. The main idea is to implement small fast caches in crossbar switches of the interconnect medium to capture and store shared data as they flow from the memory module to the requesting processor. This stored data acts as a cache for subsequent requests, thus reducing the need for remote memory accesses tremendously. The implementation of a cache in a crossbar switch needs to be efficient and robust, yet flexible for changes in the caching protocol. The design and implementation details of a CAche Embedded Switch ARchitecture, CAESAR, using wormhole routing with virtual channels is presented. We explore the design space of switch caches by modeling CAESAR in a detailed execution driven simulator and analyze the performance benefits. Our results show that the CAESAR switch cache is capable of improving the performance of CC-NUMA multiprocessors by up to 45 percent reduction in remote memory accesses for some applications. By serving remote read requests at various stages in the interconnect, we observe improvements in execution time as high as 20 percent for these applications. We conclude that switch caches provide a cost-effective solution for designing high performance CC-NUMA multiprocessors.

In this paper, the impact of memory management policies and switch design alternatives on the application performance of cache-coherent nonuniform memory access (CC-NUMA) multiprocessors is studied in detail. Memory management plays an important role in determining the performance of NUMA multiprocessors by dictating the placement of data among the distributed memory modules. We analyze memory traces of several scientific applications for three different memory management techniques, namely buddy, round-robin, and first-touch policies, and compare their memory system performance. Interconnection network switch designs that consider virtual channels and varying number of input buffers per switch are presented. Our performance evaluation is based on execution-driven simulation methodology to capture the dynamic changes in the network traffic during execution of the applications. It is shown that the use of cut-through switching with buffers and virtual channels can Improve the average message latency tremendously. However, the choice of memory management policy affects the amount of network traffic and the network access pattern. Thus, we vary the memory management policy and confirm the performance benefits of improved switch designs. Results of sensitivity studies by varying switch design parameters, cache block size, and memory page size are also presented. We find that a combination of first-touch memory management policy and a switch design with virtual channels and increased buffer space can reduce the average message latency by as high as 70 percent.

Cache coherent non-uniform memory access (CC-NUMA) multiprocessors continue to suffer from remote memory access latencies due to comparatively slow memory technology and data transfer latencies in the interconnection network. We propose a novel hardware caching technique, called switch cache. The main idea is to implement small fast caches in crossbar switches of the interconnect medium to capture and store shared data as they flow from the memory module to the requesting processor. This stored data acts as a cache for subsequent requests, thus reducing the latency of remote memory accesses tremendously. The implementation of a cache in a crossbar switch needs to be efficient and robust, yet flexible for changes in the caching protocol. The design and implementation details of a CAche Embedded Switch ARchitecture, CAESAR, using wormhole routing with virtual channels is presented. Using detailed execution-driven simulations, we find that the CAESAR switch cache is capable of improving the performance of CC-NUMA multiprocessors by reducing the number of reads served at distant remote memories by up to 45% and improving the application execution time by as high as 20%. We conclude that the switch caches provide a cost-effective solution for designing high performance CC-NUMA multiprocessors.

Switch design for interconnection networks plays an important role in the overall performance of multiprocessors and computer networks. In this paper we study the impact of one parameter in the switch design space, link arbitration. We demonstrate that link arbitration can be a determining factor in the performance of current networks. Moreover, we expect increased research focus on arbitration techniques to become a trend in the future, as switch architectures evolve towards increasing the number of virtual channels and input ports. In the context of a state-of-the-art switch design we use both synthetic workload and execution driven simulations to compare several arbitration policies. Furthermore, we devise a new arbitration method, Look-Ahead arbitration. Under heavy traffic conditions the Look-Ahead policy provides important improvements over traditional arbitration schemes without a significant increase in hardware complexity. Also, we propose a priority based policy that is capable of reducing the execution time of parallel applications. Lastly, we enhance the arbitration policies by a supplemental mechanism, virtual channel reservation, intended to alleviate the hot-spot problem.

As processor technologycontinues to advance at a rapid pace, the principal performance bottleneck of shared memory systems has become the memory access latency.In order to understand the effects of cache and memory hierarchy on system latencies, performance analysts perform benchmark analysis on existing state-of-the-art multiprocessors.In this study, we present a detailed comparison of the memory system of two recent commercial ventures, the HP V-Class and the SGI Origin 2000.Our goal is to compare and contrast design techniques used in these multiprocessors to tolerate the effect of memory latency.Our experimental methodology uses microbenchmarks as well as scientific applications to characterize the user-level performance.Recent

Directory schemes have long been used to solve the cache coherence problem for large scale shared memory multiprocessors. In addition, tree-based protocols have been employed to reduce the directory size and the invalidation latency for a large degree of data sharing in the system. However, the existing tree-based protocols involve a very high communication overhead for maintaining a balanced tree, especially when the degree of data sharing is low. This paper presents a new tree-based cache coherence protocol which is a hybrid of the limited directory and the linked list schemes. By utilizing a limited number of pointers in the directory, the proposed protocol connects the nodes caching a shared block in a tree fashion without incurring any communication overhead. In addition to the low communication overhead, the proposed scheme also possesses the advantages of the existing bit-map and tree-based linked list protocols, namely, scalable memory requirement and logarithmic invalidation latency. We evaluate the performance of our protocol by running four applications on the Proteus execution-driven simulator. Our simulation results show that the performance of the proposed protocol is very close to that of the full-map protocol.

Switch design for interconnection networks plays an important role in the overall performance of multiprocessors and computer networks. In this paper, a new switch design, namely FC-CB, is proposed that offers low average message latency and high throughput over a wide range of input workloads. The FC-CB switch incorporates wormhole routing and virtual channels with a full crossbar connection. Its structure is based on a novel circular buffer design with dynamic allocation. We have performed extensive simulations to compare its performance with other alternatives. Our results show that the proposed design is superior in terms of latency and throughput, especially for heavy input traffic rate and low buffer space.

A multistage bus network (MEN) is proposed to overcome some of the shortcomings of the conventional multistage interconnection networks (MINs), single bus, and hierarchical bus interconnection networks. The MBN consists of multiple stages of buses connected in a manner similar to the MINs and has the same bandwidth at each stage. A switch in an MBN is similar to that in a MIN switch except that there is a single bus connection instead of a crossbar. MBNs support bidirectional routing and there exists a number of paths between any source and destination pair. The authors develop self routing techniques for the various paths, present an algorithm to route a request along the path with minimum distance, and analyze the probabilities of a packet taking different routes. Further, they derive a performance analysis of a synchronous packet-switched MBN in a distributed shared memory environment and compare the results with those of an equivalent bidirectional MIN (BMIN). Finally, they present the execution time of various applications on the MBN and the BMIN through an execution-driven simulation. They show that the MBN provides similar performance to a BMIN while offering simplicity in hardware and more fault-tolerance than a conventional MIN.

In this paper, performance of wormhole routed 2-D torus network with virtual channels has been evaluated for cachecoherent shared-memory multiprocessors with executiondriven simulation. The traffic in such systems is very different from the traffic in message-passing environment. We show the impact of number of virtual channels, flit buffers per virtual channel, and internal links. The study shows that 4 virtual channels per link is most efficient for 2-D torus networks. The number of flit buffers per virtual channel has a considerable impact and 2 to 4 flit buffers are usually enough. The number of internal links makes a difference on the performance for applications, such as MP3D, that generate large contention for shared variables. 1 Introduction Large-scale shared-memory multiprocessors are difficult to design but they provide a unified view of the memory for easy programming. These systems are built using processormemory nodes that are connected through an interconnection network...

System-level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Efficient diagnosis is highly desirable for sustaining the original system power. Moreover, effective diagnosis is particularly important for a multiprocessor system with high scalability but low connectivity. Most of the existing results are not applicable in practice because of the high diagnosis cost and limited diagnosability. Over-d fault diagnosis, where d is the diagnosability, has only been addressed using a probabilistic method in the literature. Aiming at these two issues, we propose a hierarchical adaptive system-level diagnosis approach for hypercube systems using a divide-and-conquer strategy. We first propose a conceptual algorithm HADA to formulate a rigorous analysis. Then we present its practical variant IHADA. In HADA and IHADA, the over-d fault problem is inherently tackled through a deterministic method. Three measures for diagnosis cost (diagnosis time, number of tests, and number of test links) are analyzed for the proposed algorithms. It is proved that the diagnosis cost required by our approach is lower than in previous diagnosis algorithms. It is shown that the diagnosis cost for the proposed algorithms depends on the number and location of faulty units in the system and the cost is extremely low when only a small number of faulty units exist. It is also shown that our algorithms are characterized by lower costs than a pessimistic diagnosis algorithm which trades lower diagnosis cost for a lower degree of accuracy. Experimental results on the nCUBE are provided.

This paper presents a unified model for analyzing multistage interconnection networks with multi-queue buffered strategies. Buffering strategies include SAFC (statically allocated fully connected), SAMQ (statically allocated multi-queue), DAMQ (dynamically allocated multi-queue), and DAFC (dynamically allocated fully connected) schemes. We develop a unified model to evaluate the performance of all these buffer allocation schemes under both uniform and nonuniform traffic patterns. The analytical model is validated through extensive simulations. Using the unified model, we conducted performance comparisons on the four buffer allocation schemes. It is shown that the DAFC scheme has the best performance over all the four buffer allocation schemes under both uniform and nonuniform loads.

Parallel applications differ from significant bus traffic due to the transfer of shared data. Large block sizes exploit locality and decrease the effective memory access time. It also has a tendency to group data together even though only a part of it is needed by any one processor. This is known as the false sharing problem. This research presents a dynamic sub-block coherence protocol which minimizes false sharing by trying to dynamically locate the point of false reference. Sharing traffic is minimized by maintaining coherence on smaller blocks (sub-blocks) which are truly shared, whereas larger blocks are used as the basic units of transfer. Larger blocks exploit locality while coherence is maintained on sub-blocks which minimize bus traffic due to shared misses. The simulation results indicate that the dynamic sub-block protocol reduces the false sharing misses by 20 to 30 percent over the fixed sub-block scheme.

In this brief contribution, we derive an exact expression for (n-1)-cube reliability in an n-cube using a new probability fault model and an existing random fault model. Approximate results are also obtained for m-cube reliability for values of m smaller than n-1. We show that the proposed probability model for computing subcube reliability is equally accurate, but computationally more efficient than the existing random fault model.>

We study the problem of constructing subcubes in faulty hypercubes. First a divide-and-conquer technique is used to form the set of disjoint subcubes in the faulty hypercube. The concept of irregular subcubes is then introduced to take advantage of advanced switching techniques, such as wormhole routing, to increase the sizes of the available subcubes. We present a subcube partitioning technique to form an irregular subcube of maximum size. The n-cube containing two faults is studied first because, in the worst case, two faults are sufficient to destroy all the possible regular (n-1)-cubes. It is shown that the subcube partitioning technique is able to tolerate /spl Gamma/n/2/spl Gamma/ faults while maintaining a fault-free (n-1)-cube in a faulty n-cube. In general, we show that a fault-free (n-m-1)-cube is guaranteed when there are (/spl Gamma/n-m/2/spl Gamma/+1)/spl times/2/sup m/+2/sup m-1/-1 or fewer faults. We also develop a two-phase subcube allocation strategy in order to show the average case performance of our subcube construction technique. Extensive simulation is conducted to show the effectiveness of the two-phase subcube allocation strategy.>

A Multistage Bus Network(MBN) has been proposed as a viable alternative to the existing interconnection networks. The MBN consists of multiple stages of buses connected in a manner similar to the conventional Multistage Interconnection Networks(MINs) and has the same bandwidth at each stage. Due to the bidirectional nature of the MBN, there exist a number of separate paths between any source and destination pair. Some paths make a U-turn at an intermediate stage switch which is a common ancestor of the source and destination. We present self routing techniques for the various paths. We also present a performance analysis of a synchronous packet switched MBN and compare the results with those of a MIN. Finally we present a reliability analysis of the MBN and show its superiority over the MIN.

This paper proposes a distributed directory cache coherence protocol and compares the performance of the proposed protocol with fully mapped and single linked list protocols for the hypercube multiprocessors. The directories of shared blocks are maintained as a tree structure which is motivated by the similarity of the indirect binary n-cube to the direct binary n-cube. The proposed protocol also takes advantage of the wormhole routing technique. Compared to the fully mapped and single linked list schemes, the proposed protocol reduces the memory reference latency and the network traffic.

Large scale shared memory multiprocessors use a directory based cache coherence scheme. The basic directory scheme, called full-map, is efficient but has a large memory overhead. Therefore, limited directory schemes have been proposed which limit the number of pointers in the directories. These schemes tradeoff smaller memory overhead for larger memory access latencies. We propose a new limited directory scheme, which achieves lower memory overhead as well as smaller memory access latencies. The scheme uses ring embedding in a hypercube in conjunction with wormhole routing to reduce the invalidation delays. The proposed scheme performs as good as full-map for smaller degree of sharing and performs better than full-map for larger degree of sharing.>

Proposes an analysis technique for a class of Multistage Interconnection Networks (MIN's) that have finite buffers at their switch inputs and operate in a synchronous packet-switched mode. The authors examine the issue of clock period in design and analysis of synchronous MIN's and propose a model based on small clock periods. Then they analyze their "small cycle" design and compare the results with those obtained from the standard "big cycle" model that is currently used. The significant performance improvement of their model is shown based on various clock width, data width, and buffer length.>

The subcube allocation problem in faulty hypercubes is studied in this paper. An efficient method for forming the set of regular subcubes is proposed. A concept of irregular subcubes is then introduced to take advantage of the advanced switching techniques such as wormhole routing to increase the size of available sub cubes. In this paper, a two-phase fault tolerant subcube allocation strategy is proposed. The first phase is the re configuration process based on a modified subcube parti tioning technique which finds the set of disjoint subcubes in the faulty hypercube. The second phase is to apply an existing fault-free subcube allocation strategy such as Buddy strategy to each disjoint subcube for assigning the fault-free available subcubes to the incoming tasks. The simulation results using Buddy strategy are also given.

In this paper, we propose an adaptive scan (AS) strategy for submesh allocation. The earlier frame sliding (FS) strategy allocates submeshes based on fixed orientations of incoming faska. It also slides fiunaes om mesh planes by fdzed strides. Our AS a1Iocation strategy differs from the FS strategy in the following two ways: (1) it does not fiz the orientations of incoming tasks; (2) it scans on mesh planes adapfively. Experimental studies show that our AS strategy outperforms the FS strategy in terms of external fragmentation, completion time, and processor uitilizaiion.

Traditional adaptive centralized system diagnosis assumes a fully connected network topology, hence it can not be used in a number of classes of multiprocessor systems, such as meshes. This paper proposes an adaptive system-level diagnosis algorithm for meshes with wraparound, such as Intel Paragon machine. It is proved that the diagnosis cost required by the proposed approach is lower than the known diagnosis algorithms which can be applied to mesh architectures. Also over-d fault problem can be efficiently solved by our method, where d is the diagnosability.

Shared memory multiprocessors with cache require careful consideration of cache parameters while implementing an algorithm to obtain optimal performance. In this paper, we study the implementation of some existing FFT algorithms and analyze the number of cache misses based on the problem size, number of processors, cache size, and block size. We also propose a new FFT algorithm which minimizes the number of cache misses.

A directory of state information is introduced into a multistage interconnection network (MIN) switch, and a multiple copy cache coherence protocol is developed. It is shown that the protocol is better than a single copy protocol on this MIN with directories (MIND) scheme. A network called the multistage bus network (MBN), which introduces a bus and multiple snoopers into the switches of a MIN, is presented. The snooping buses form multiple trees with the memories at the roots and the processors at the leaves. Each switch contains directories to hold state information on the shared blocks that is used to filter the coherence traffic from one level to another. The shared requests pass through the directories, whereas the private requests pass directly from the bus in one level to the bus in the next level. Analytical and simulation models for these multistage cache coherent architectures are developed. Both the MIND and the MBN schemes are studied with a simple multiple copy protocol. The results show that the MBN scheme performs better than the MIND or conventional scheme.>

System decomposition is a novel technique for modeling the dependability of complex systems without constructing a single-level Markov Chain (MC). This is demonstrated in this paper for the availability computation of a class of multiprocessors that uses 4*4 switching elements for the multistage interconnection network (MIN). The availability model is known as task-based availability, where a system is considered operational as long as the task requirements are satisfied. The authors develop two simple MC's for the processors and memories and solve them using a software package, called HARP. The probabilities of i processing elements (PE's) and j memory modules (MM's) working at any time t, denoted as Pi(t) and Pj(t), are obtained from their corresponding MC's. The effect of the MIN is captured in the model by finding the number of switches required for the connection of i PE's and j MM's. A third MC is then developed for the switches to find the probability that the MIN provides the required (i*j) connection. Multiplying this term with Pi(t) and Pj(t), the probability of an (i*j) working group is obtained. The methodology is generalized to model arbitrary as well as larger size systems. Transient and steady state availabilities are computed for a variety of MIN configurations and the results are validated through simulation.>

The authors present a technique to compute the communication times of programs on cache coherent distributed shared memory systems. Simulated annealing is used to obtain near-optimal mappings of program tasks onto processors. Various cost parameters are explored for determining efficient mappings of the program tasks onto the processors in the presence of cache coherence protocols. The techniques were demonstrated using the Sequent Balance multiprocessor and the Jacobi iteration problem. Measurement results confirm that the estimate of communication time is fairly accurate. The importance of accurate estimation of communication time for efficient mapping of program tasks in the presence of the cache coherence protocol was verified using measurements on the Balance multiprocessor.>

A large scale, cache-based multiprocessor that is interconnected by a hierarchical network such as hierarchical buses or a multistage interconnection network (MIN) is considered. An adaptive cache coherence scheme for the system is proposed based on a hardware approach that handles multiple shared reads efficiently. The new protocol allows multiple copies of a shared data block in the hierarchical network, but minimizes the cache coherence overhead by dynamically partitioning the network into sharing and nonsharing regions based on program behavior. The new cache coherence scheme effectively utilizes the bandwidth of the hierarchical networks and exploits the locality properties of parallel algorithms. Simulation experiments have been carried out to analyze the performance of the new protocol. The simulation results show that the new protocol gives 15% to 30% performance improvement over some existing cache coherence schemes on similar systems for a wide range of workload parameters.>

A detailed analytical and simulation model that accurately captures the effect of communication delay for local area networks is presented. To demonstrate the framework, load sharing algorithms are presented and evaluated both with and without the effect of the communication network delay. The algorithms use the Ethernet communication protocol to their advantage and provide superior performance compared to several published algorithms. The strong performance results for the new algorithms demonstrate that a load sharing algorithm can cooperate rather than compete with a communication network.>

Performance analyses of packet-switched multiple-bus multiprocessor systems are presented. Approximate queuing network models are developed for both synchronous and asynchronous control schemes, and the results are shown to be in good agreement with simulation results. The analysis of the synchronous system is based on a decomposition technique, with each of the shared resources in the system being represented as a single-server queue. For asynchronous systems, the analysis is based on the flow equivalence technique. Numerical results obtained from the analyses indicate that packet-switched multiple-bus multiprocessors with only a few buses perform almost as well as crossbar-based multiprocessors.>

The formulation and validation of an analytical approach for the performance evaluation of the Manchester dataflow computer is discussed. The analytical approach is based on closed queuing network models. The average parallelism of the dataflow graph being executed on the dataflow architecture is shown to be related to the population of the closed network. The model of the dataflow computer is validated by comparing the analytical results to those obtained from the prototype Manchester dataflow computer and from simulation. The bottleneck centers in the prototype machine have been identified through the model, and various architectural modifications have been investigated from performance considerations.>

An algorithm to map a multistage interconnection network (MIN) onto a systolic array is developed. The algorithm provides a systematic approach that lays out a cube MIN in a compact area. An area-delay analysis is presented and is compared with that of a crossbar. It is shown that the cube MIN performs better than crossbar in both area and delay.>

This paper presents analytical results of computation-communication issues in dynamic dataflow architectures. The study is based on a generalized architecture which encompasses all the features of the proposed dynamic dataflow architectures. Based on the idea of characterizing dataflow graphs by their average parallelism, a queueing network model of the architecture is developed. Since the queueing network violates properties required for product from solution, a few approximations have been used. These approximations yield a multi-chain closed queueing network in which the population of each chain is related to the average parallelism of the dataflow graph executed in the architecture. Based on the model, we are able to study the effect on the performance of the system due to factors such as scalability, coarse grain vs. fine grain parallelism, degree of decentralized scheduling of dataflow instructions, and locality.

Asynchronous packet-switched interconnection networks with decentralized control are very appropriate for multiprocessing and data-flow architectures. The authors present performance models of single- and multiple-ring networks based on token-ring, slotted-ring, and register-insertion-ring protocols. The multiple ring networks have the advantage of being reliable, expandable, and cost effective. An approximate and uniform analysis, based on the gate M/G/1 queuing model, has been developed to evaluate the performance of both existing single-ring networks and the proposed multiple-ring networks. Approximations are good for low and medium load. The analyses are based on symmetric ring structure with nonexhaustive service policy and infinite queue length at each station. They essentially involve modeling of queues with single- and multiple-walking servers. The results obtained from the analytical models are compared to those obtained from simulation.>

Analytical models are developed for seven existing cache protocols, namely, Write-Once, Write-Through, Synapse, Berkeley, Illinois, Firefly, and Dragon. The protocols are implemented on a multiprocessor with a packet-switched shared bus. The models are based on queuing networks that consist of both open and closed classes of customers. The models incorporate the requests for invalidation signals, write-through, and write-back operations, and the solution is based on the mean value analysis (MVA) algorithm. The performance of these protocols under various system parameters is compared on the basis of the models. It is found that Firefly and Dragon perform better than the others.>

A discussion is presented of multiple-token-ring networks. Based on different packet transmission schemes, three protocols are discussed: (i) separate queues with simultaneous transmissions, (ii) single queue with simultaneous transmissions, and (iii) single queue with single transmission. The interface design and the approximate analyses are presented for all of the three protocols.>

Dataflow computers are an alternative to the von Neumann architectures and are capable of exploiting large amount of parallelism inherent in many computer applications. This paper deals with the performance analysis of the Manchester dataflow computer based on queueing network models. The model of the dataflow computer has been validated by comparing the analytical results with those obtained from the prototype Manchester dataflow computer. The bottleneck centers in the prototype machine have been identified through the model and various architectural modifications have been investigated both from performance and reliability viewpoints.

An interference analysis of the interconnection networks (IN's) for tightly coupled multiprocessors is presented in this correspondence. The interconnections considered are crossbars and delta networks. Two situations are examined: when a memory module is equally likely to be addressed by a processor and when a processor has a favorite memory. It is shown that for a higher rate of favorite requests, the delta networks perform close to a crossbar.

The effect of failures on the performance of multiple-bus multiprocessors is considered. Bandwidth expressions for this architecture are derived for uniform and nonuniform memory references. Mathematical models are developed to compute the reliability and the performance-related bandwidth availability (BA). The results obtained for the multiple-bus interconnection are compared with those of a crossbar. The models are also extended to analyze the partial bus structure, where the memories are divided into groups and each group is connected to a subset of buses. The reliability and the BA of the multiple-bus and partial bus architectures are compared.

A Processing Element (PE) essentially consists of a processor and a memory module. A loosely coupled multiprocessor is comprised of a set of such PEs interconnected through an Interconnection Network (IN). The design of the IN is crucial to an efficient communication beween the PEs. This paper presents approximate evaluations of two loosely coupled architectures, each having three types of INs, namely: shared bus, crossbar and a class of Multistage Interconnection Networks (MINS) called Omega network. Probability of Acceptance (PA) of a message is considered as a measure of the performance. For a high rate of internal requests, it is shown that an Omega network performs close to a crossbar while reducing the the cost of interconnection to a large extent.

A general class of hypercube structures is presented in this paper for interconnecting a network of microcomputers in parallel and distributed environments. The interconnection is based on a mixed radix number system and the technique results in a variety of hypercube structures for a given number of processors N, depending on the desired diameter of the network. A cost optimal realization is obtained through a process of discrete optimization. The performance of such a structure is compared to that of other existing hypercube structures such as Boolean n-cube and nearest neighbor mesh computers.

This paper introduces a general class of self-routing interconnection networks for tightly coupled multiprocessor systems. The proposed network, named a "generalized shuffle network (GSN)," is based on a new interconnection pattern called a generalized shuffle and is capable of connecting any number of processors M to any number of memory modules N. The technique results in a variety of interconnection networks depending on how M nd N are factored. The network covers a broad spectrum of interconnections, starting from shared bus to crossbar switches and also includes various multistage interconnection networks (MIN's).

A decimation-in-time radix-2 fast Fourier transform (FFT) algorithm is considered here for implementation in multiprocessors with shared bus, multistage interconnection network (MIN), and in mesh connected computers. Results are derived for data allocation, interprocessor communication, approximate computation time, and speedup of an N point FFT on any P available processing elements (PE's). Further generalization is obtained for a radix-r FFT algorithm. An N X N point two-dimensional discrete Fourier transform (DFT) implementation is also considered when one or more rows of the input data matrix are allocated to each PE.

A new class of general topologies is proposed in this paper for interconnecting a large network of computers in parallel and distributed environment. These structures have been shown to possess small internode distances, fairly low number of links per node, easy message routing and large number of alternate paths that can be used in case of faults in the system. The interconnection is based on a mixed radix number system, presented in this paper. The technique results in a variety of structures for a given number of processors N, depending on the required diameter in the network. A bus oriented structure is also introduced here, based on the same mathematical framework. These structures possess only two I/O ports per processor and are also shown to have small internode distances.

In this correspondence we derive algorithms for multioperand addition of Koren's generalized number system. A carry-lookahead adder for fast addition of two operands in generalized binary numbers is developed. Truncation errors for this type of representation are examined and rounding algorithms are presented to reduce these errors.