Compute eXpress Link (CXL) has emerged as a key enabler of memory disaggregation for future heterogeneous computing systems to expand memory on-demand and improve resource utilization. However, CXL is still in its infancy stage and lacks commodity products on the market, thus necessitating a reliable system-level simulation tool for research and development. In this paper, we propose CXL-DMSim1, an open-source full-system simulator to simulate CXL disaggregated memory systems with high fidelity at a gem5-comparable simulation speed. CXL-DMSim incorporates a flexible CXL memory expander model along with its associated device driver, and CXL protocol support with CXL.io and CXL.mem. It can operate in both app-managed mode and kernel-managed mode, with the latter using a dedicated NUMA-compatible mechanism. The simulator has been rigorously verified against a real hardware testbed with both FPGA- and ASIC-based CXL memory devices, which demonstrates the qualification of CXL-DMSim in simulating the characteristics of various CXL memory devices at an average simulation error of 3.4%. The experimental results using LMbench and STREAM benchmarks suggest that the CXL-FPGA memory exhibits a ~2.88× higher latency than local DDR while the CXL-ASIC latency is ~2.18×; CXL-FPGA achieves 45-69% of local DDR memory bandwidth, whereas the number for CXL-ASIC is 82-83%. The study also reveals that CXL memory can significantly enhance the performance of memory-intensive applications, improved by 23× at most with limited local memory for Viper key–value database and approximately 60% in memory-bandwidth-sensitive scenarios such as MERCI. Moreover, the simulator’s observability and expandability are showcased with detailed case-studies, highlighting its great potential for research on future CXL-interconnected hybrid memory pool.

The victim cache was originally designed as a secondary cache to handle misses in the L1 data (L1D) cache in CPUs. However, this design is often sub-optimal for GPUs. Accessing the high-latency L1D cache and its victim cache can lead to significant latency overhead, severely degrading the performance of certain applications. We introduce HIVE, a high-priority victim cache designed to accelerate GPU memory accesses. HIVE handles memory requests first, before they reach the L1D cache. Our experimental results show that HIVE achieves an average performance improvement of $\mathbf{7 7. 1 \%}$ and $\mathbf{2 1. 7 \%}$ compared to the baseline and the state-of-the-art architecture, respectively.

Large Language Models (LLMs) inference have gained popularity over the past two years, driven by their high performance achieved through rapid increases in the number of parameters. The inference process of LLMs consists of two distinct stages: prefill and decode, each with unique computational characteristics. While existing neural network inference platforms, such as Google's TPU, perform well during the prefill stage, they often suffer from poor resource utilization during the decode stage. To address this challenge, we propose the scalable Headtile architecture, specifically designed to improve hardware resource utilization. By analyzing the inference behavior of LLMs, we examine how each layer executes on TPUv3 and introduce the Maarg paradigm in Headtile for inter-layer scheduling and mapping. Experimental results show that Headtile can achieve up to 24 × higher throughput in the decode stage compared to TPUv3. In addition, the Maarg paradigm reduces memory accesses by up to 60 % during the prefill stage.

In recent years, new methods for solving partial differential equations (PDEs) such as Monte Carlo random walk methods have gained considerable attention. However, due to the lack of hardware-intrinsic randomness in the conventional von Neumann architecture, the performance of PDE solvers is limited. In this paper, we introduce NeuroPDE, a hardware design for neuromorphic PDE solvers that utilizes emerging spintronic and ferroelectric devices. NeuroPDE incorporates spin neurons that are capable of probabilistic transmission to emulate random walks, along with ferroelectric synapses that store continuous weights non-volatilely. The proposed NeuroPDE achieves a squared error of less than 1e-2 compared to analytical solutions when solving diffus3.48× to 315× speedup in execution time and an energy consumption advantage of 2.7× to 29.8× over advanced CMOS-based neuromorphic chips. By leveraging the inherent physical stochasticity of emerging devices, this study paves the way for future probabilistic neuromorphic computing systems.

Deadlock-free adaptive routing is extensively adopted in both on-chip and off-chip interconnection networks to improve communication bandwidth and reduce latency. Introducing virtual channels (VCs), also known as virtual lanes (VLs). This is the mainstream technique to handle deadlocks incurred by adaptive routing and also provides VC preemption for higher priority traffic. However, existing deadlock-free flow control schemes either underutilize memory resources due to inefficient buffer management to simplify hardware implementation, or rely on complicated global coordination and synchronization with very high hardware complexity. Most hardware-friendly schemes use more VCs and memory resources to enable ease of implementation of deadlock-free flow control. In contrast, sophisticated schemes achieve deadlock freedom with minimum VC cost, even eliminating additional buffer requirement through the complicated control mechanisms. In this work, we rethink the root cause of the deadlock problem from a different perspective by considering it as a lack of credit, which makes us find an efficient solution to the deadlock problem. With minor modification of credit accumulation and return, our proposed bubble-swap flow control (BSFC) ensures atomic buffer swap between two adjacent routers only based on local credit status while making full use of the buffer space. BSFC achieves a better tradeoff between implementation complexity and memory overhead and can be easily integrated in the industrial router with no modification on buffer allocation or port arbitration. The simulation results demonstrate BSFC outperforms existing bubble-based deadlock-free methods by average 64% higher throughput. We further propose a credit reservation strategy to eliminate the escape virtual channel (VC) cost for fully adaptive routing implementation. The synthesizing results demonstrate that BSFC along with credit reservation (BSFC-CR) can reduce the area and power consumption by respectively 29% and 26% in contrast to the traditional critical bubble scheme (CBS).

Deep learning becomes increasingly popular, and its main workload is Sparse-Sparse Matrix Multiplication (SpMSpM). Most SpMSpM accelerators usually only support a single dataflow. Different dataflows have different performance in different computing environments. Therefore, the single-dataflow accelerator cannot maintain the highest performance in all environments. Compared with single-dataflow accelerators, multi-dataflow accelerators provide flexible options for different workloads and improve the overall performance. Flexagon, Sparm, and SPADA are state-of-the-art multi-dataflow accelerators. However, the computation process of Flexagon and Sparm is not fully pipelined, and SPADA cannot support inner product dataflow. Additionally, Flexagon, Sparm, and SPADA cannot switch dataflows quickly and accurately. Inspired by these observations, we present SpMARD, a SpMSpM accelerator with reconfigurable dataflow. The computation process of SpMARD is fully pipelined, and SpMARD can support six dataflow variants simultaneously. Through the design of a Two-stage Pipeline Adder Network (TPAN) and a Position-based Psum Array (PPA), SpMARD can execute element-level merging, which can hide the merging overhead. Through the quantitative analysis of dataflows, we implement a Dataflow Switcher (DSwitcher), which can switch dataflows more efficiently. For the SpMSpM workload, the performance (GOPS) of the SpMARD we proposed is 1.27 times that of Flexagon, 1.18 times that of Sparm, and 1.22 times that of SPADA.

Resistive Random Access Memory (ReRAM) based architectures have shown great potential for realizing energy-efficient Deep Neural Network (DNN) acceleration. When deploying a DNN, the ReRAM-based designs need a scheduling scheme to translate massive hardware resources into actual performance. Different scheduling schemes would lead to different levels of data reuse and computational parallelism, resulting in different energy efficiency and performance. However, the ReRAM-based scheduling scheme faces the following limitations. First, current studies mainly focus on intra-layer scheduling scheme optimizations by using the Weight Stationary (WS) data flow. These studies ignore the difference between layers and limit optimization opportunities. Second, there is no systematic definition and analysis for inter-layer scheduling schemes. Third, there is no co-optimization study on intra- and inter-layer scheduling schemes. Fourth, the complex network structure leads to intricate inter-layer data dependency, making the optimization of the scheduling scheme more challenging. These limitations restrict the comprehensive understanding of the scheduling schemes.Inspired by these observations, we identify the fundamental impact of intra-layer scheduling schemes on ReRAM-based designs, including the WS and Input Stationary (IS) data flows. We also systematically define and analyze inter-layer scheduling schemes according to different combinations of data flows, including the WS-WS, IS-IS, WS-IS, and IS-WS data flows. We analyze and explore different resource allocation strategies for these schemes. We also propose the intra- and inter-layer co-optimization to further improve performance and energy efficiency. Then, we propose a method for building a hybrid scheduling scheme by flexibly combining these inter-layer scheduling schemes for complex networks. Finally, we seek the potential to improve performance and energy efficiency for hybrid scheduling schemes. For deploying the MobileNet-V1, ResNet-18, VGG-16, and AlexNet, the hybrid scheduling scheme improves performance by 10.2×~130.7×, 1.9×~16.5×, 7.0×~56×, and 1×~153.1× than the WS-WS, IS-IS, IS-WS, and WS-IS based scheduling schemes, respectively. Similarly, the power efficiency can also be increased by 15× and 26× than the WS-WS and IS-IS based scheduling schemes, respectively.

The processing-in-memory (PIM) architecture becomes a promising candidate for deep learning accelerators by integrating computation and memory. Most PIM-based studies improve the performance and energy efficiency by using the weight stationary (WS) data flow due to its high parallelism. However, the WS data flow has some fundamental limitations. First, the WS data flow has huge activation movements between on-chip memory and off-chip memory due to the limited memory space of the resistive random-access memory (ReRAM) array. Second, the WS data flow needs to read the input activation repeatedly according to the convolution window. These data movements decrease the energy efficiency and performance of the PIM architecture. To address these issues, the input stationary (IS) data flow stores activations instead of weights to reduce data movements. But the IS data flow faces some challenges. First, the data dependency between adjacent layers limits the performance. Second, there are huge across-array computations due to the special mapping method. Third, the previous IS data flow cannot realize the high parallelism. Fourth, the IS data flow depends on the 3-D ReRAM structure. To address these issues, we propose a novel data flow for PIM architectures. We optimize the IS data flow to decrease the activation movement and propose a parallel computing method to realize high parallelism and reduce the across-array computations. We identify and analyze the fundamental limitations and impact of different interlayer data flows, including the WS-WS, IS-IS, WS-IS, and IS-WS. We also propose a method to build a hybrid data flow by combining these interlayer data flows to tradeoff performance and energy consumption. Our experimental results and analysis demonstrate the potential of our design. The performance and energy efficiency of our design reach 0.13–1.77 TFLOPS and 61–85 TOPS/J, respectively. Compared to the state-of-the-art design, the NEBULA, our design can improve performance by$1.4\times $,$2.3\times $, and$3.5\times $for deploying the MobileNet-V1, ResNet-18, and VGG-16, and also can improve energy efficiency by$3.3\times $,$2\times $, and$2\times $, respectively.

As the main workload of many scientific and machine learning applications, sparse matrix-matrix multiplication (spGEMM) has become a hot research field. The current spG EMM workloads exhibit sparsity and irregularity, leading to computational inefficiencies on traditional hardware platforms and motivating numerous customized accelerators. These spe-cialized hardware designs typically accelerate only one type of spGEMM dataflow (such as Inner-Product, Outer-Product, or Gustavson), yet the computational efficiency of the same spG EMM kernel can vary significantly under different dataflows. Flexagon is the first spGEMM accelerator to support multiple dataflows, but its MRN (Merger-Reduction Network) design causes a lot of data blocking and load imbalance, which limits its performance. In this work, we propose Sparm, which achieves efficient merging of psums (partial sums) for different dataflows through a specialized indexing unit. Sparm addresses the performance bottlenecks encountered by Flexagon when facing highly sparse matrices. Furthermore, Sparm employs a row/column prefetcher to load the streaming matrices proactively and thus significantly reduces the amount of DRAM access. We conduct simulations using a cycle-accurate simulator on workloads from various application domains, and the results demonstrate that Sparm achieves average performance gains of 2.62× and 1.35× compared to state-of-the-art spGEMM accelerators SIGMA and Flexagon. Meanwhile, Sparm brings only a small amount of additional hardware overhead over Flexagon.

Value prediction is a microarchitectural technique that enhances processor performance by speculatively breaking true data dependencies. It has demonstrated improved performance in both single-threaded and multi-threaded workloads, rendering it an appealing microarchitectural approach. While high-performance value predictors can achieve impressive accuracy, they may also incur significant costs in terms of area, power consumption, and complexity. Therefore, there is a demand for lightweight value prediction techniques capable of striking a favorable balance between performance and overhead. However, designing value predictors with superior performance using limited resources presents an urgent challenge. Consequently, this work proposes a design space exploration framework for the state-of-the-art EVES value predictor, aiming to efficiently configure the design parameters of the value predictor within constrained RAM resources. Additionally, the article evaluates the performance of the explored value predictor across a wide range of workloads. The explored value predictors exhibit high efficiency across RAM sizes ranging from 2KB to 16KB while maintaining acceptable computational complexity. Furthermore, the results indicate that the explored value predictor achieves optimal efficiency under the 2KB constraint, with the highest acceleration-to-cost ratio reaching 4.02%/KB.

The Processing- In- Memory (PIM) architecture becomes a promising candidate for deep learning acceleration by integrating computation and memory. Due to the simple mapping method and high parallelism, the Weight Stationary (WS) data flow is widely used in PIM-based studies to improve performance and energy efficiency. However, the WS data flow leads to huge activation movements, becoming the bottleneck for reducing latency and energy consumption. To address this issue, the Input Stationary (IS) data flow stores activations instead of weights in the PIM architecture to reduce data movements. However, the traditional IS data flow also faces several challenges. First, the inter-layer data dependence and imbalance workload decrease pipeline efficiency. Second, the across-array computation reduces energy efficiency and performance. Third, the traditional IS data flow relies on the 3D ReRAM structure. Inspired by these observations, we propose a Hybrid data flow for PIM Architectures, named HPA. The HPA contains novel intra-layer and inter-layer data flows, named the PP-IS data flow and the IS- WS hybrid data flow, respectively. The PP- IS data flow optimizes the data mapping strategy and computing method to reduce activation movements. In addition, the PP- IS data flow uses the parallel computing method to decrease across-array computations. Based on the novel intra-layer data flow, we propose the IS- WS hybrid data flow to trade off performance and energy efficiency. Finally, we optimize the pipeline for the hybrid data flow to mitigate data depen-dence and balance inter-layer workloads, improving pipeline efficiency. Our experimental results and analysis demonstrate the potential of the HPA. The performance and power efficiency of the HPA reaches 1.64$GFLOPS\sim 63$G F LO P Sand 2.1$TOPS/W\sim 151\ TOPS/W$, respectively. Compared to the state-of-the-art design, the NEBULA, the HPA can significantly improve power efficiency and performance by$22.1\times$and$7.8\times$, respectively, when deploying the MobileNet VI.

Large parallel applications have heavily used MPI (Massage Passing Interface) collectives that support portable and efficient group communication operations. MPI_Bcast is one of the most commonly used MPI collectives that broadcast data to all processes of the communication domain. However, traditional software-based broadcast algorithms fail to fully utilize modern interconnection networks’ advanced features such as offloading collectives to the network hardware for efficient group communications. Besides, the semantic gap between MPI_Bcast and hardware multicast of underlying interconnects presents challenges for offload-based algorithms to accelerate MPI_Bcast for a wide range of message sizes.In this paper, we propose a hardware-software co-design MPI_Bcast by efficiently leveraging the NIC-based collective offload provided by Tianhe-express interconnect, which completely precludes the involvement of CPU to accelerate message broadcast. We detail this broadcast mechanism that can be adaptively tuned to offload MPI_Bcast operations from the CPU to the NIC for various message and system sizes. In addition, we further propose a topology-aware broadcast design in conjunction with this offload method to significantly reduce the broadcast latency by constructing the optimal global inter-node communication tree. We implement and evaluate the proposed Tianhe-Express Offload-based Broadcast (TOB) design on Tianhe-2A and Tianhe-EP supercomputers. Extensive experiments have been conducted to evaluate TOB performance at both microbenchmark and application levels. Our solution offers up to 4.94x significant performance speedup at the microbenchmark level over state-of-the-art MPI libraries. For the application-level evaluation, our technique accelerates scientific applications by a maximum speedup of 1.34x.

In recent years, MultiModal Large Language Models (MM-LLMs), based on the Contrastive Language-Image Pretraining models (CLIP), have achieved the best results in many fields. CLIP breaks through the gaps between language models and image models, realizes zero-shot image classification, and achieves excellent performance in tasks such as text-to-image generation, image style transformation, and long video generation. However, there are few studies on the fault tolerance of CLIP with soft errors, which hinders the application of multimodal large models in the field of security. Based on the analysis of the fault tolerance of common multimodal large models, we proposes a soft error mitigation framework. According to the experiments in this paper, the framework can effectively detect soft errors and mitigate the errors.

Deep Neural Networks (DNNs) have achieved great progress in academia and industry. But they have become computational and memory intensive with the increase of network depth. Previous designs seek breakthroughs in software and hardware levels to mitigate these challenges. At the software level, neural network compression techniques have effectively reduced network scale and energy consumption. However, the conventional compression algorithm is complex and energy intensive. At the hardware level, the improvements in the semiconductor process have effectively reduced power and energy consumption. However, it is difficult for the traditional Von-Neumann architecture to further reduce the power consumption, due to the memory wall and the end of Moore’s law. To overcome these challenges, the spintronic device based DNN machines have emerged for their non-volatility, ultra low power, and high energy efficiency. However, there is no spin-based design that has achieved innovation at both the software and hardware level. Specifically, there is no systematic study of spin-based DNN architecture to deploy compressed networks. In our study, we present an ultra-efficient Spin-based Architecture for Compressed DNNs (SAC), to substantially reduce power consumption and energy consumption. Specifically, we propose a One-Step Compression algorithm (OSC) to reduce the computational complexity with minimum accuracy loss. We also propose a spin-based architecture to realize better performance for the compressed network. Furthermore, we introduce a novel computation flow that enables the reuse of activations and weights. Experimental results show that our study can reduce the computational complexity of compression algorithm from 𝒪( Tk 3 to 𝒪( k 2 log k ), and achieve 14× ∼ 40× compression ratio. Furthermore, our design can attain a 2× enhancement in power efficiency and a 5× improvement in computational efficiency compared to the Eyeriss. Our models are available at an anonymous link https://bit.ly/39cdtTa .

As the Convolutional Neural Network (CNN) goes deeper and more complex, the network becomes memory-intensive and computation-intensive. To address this issue, the lightweight neural network reduces parameters and Multiplication-and-Accumulation (MAC) operations by using the Depthwise Separable Convolution (DSC) to improve speed and efficiency. Nonetheless, the energy efficiency of classical Von Neumann architectures for CNNs is limited due to the memory wall challenge. Spin-based architectures have the potential to address this challenge thanks to the integration of memory and computing with ultra-high energy efficiency. However, deploying the DSC on spin-based architectures with the traditional dataflow leads to huge activation movements and low hardware utilization. Moreover, the inter-layer data dependency of neural networks increases latency. These factors become the bottleneck of improving energy efficiency and performance. Inspired by these challenges, we propose a novel dataflow on Spin-based Architectures for Lightweight neural networks (SAL). The novel dataflow replaces convolution unrolling by selecting activations in the crossbar according to the convolution window and also realizes the inter-layer data reuse. Moreover, the novel dataflow also reduces the latency due to the data dependency between layers, realizing higher performance. To the best of our knowledge, this is the first design to use hybrid dataflow for the PIM architecture. We also optimize the structure of the spin-based crossbar and the pipeline based on the dataflow to achieve better data reuse and computational parallelism. For deploying the MobileNet V1, the novel dataflow improves the hardware utilization by 23×∼ 105× and reduces the data traffic by 1.09×∼ 18.6×. Compared with the NEBULA, a spin-based non-Von Neumann architecture, the SAL reduces the energy consumption by 4× and improves the performance by 7.3×, which are 0.32 mJ and 10.43 GOPs -1 , respectively. Moreover, the SAL improves power efficiency over 29 times more than the NEBULA. Compared with the Eyeriss, the SAL improves the energy efficiency by four orders of magnitude.

Deep learning has become a highly popular research field, and previously deep learning algorithms ran primarily on CPUs and GPUs. However, with the rapid development of deep learning, it was discovered that existing processors could not meet the specific large-scale computing requirements of deep learning, and custom deep learning accelerators have become popular. The majority of the primary workloads in deep learning are general matrix-matrix multiplications (GEMMs), and emerging GEMMs are highly sparse and irregular. The TPU and SIGMA are typical GEMM accelerators in recent years, but the TPU does not support sparsity, and both the TPU and SIGMA have insufficient utilization rates of the Processing Element (PE). We design and implement SparGD, a sparse GEMM accelerator with dynamic dataflow. SparGD has specific PE structures, flexible distribution networks and reduction networks, and a simple dataflow switching module. When running sparse and irregular GEMMs, SparGD can maintain high PE utilization while utilizing sparsity, and can switch to the optimal dataflow according to the computing environment. For sparse, irregular GEMMs, our experimental results show that SparGD outperforms systolic arrays by 30 times and SIGMA by 3.6 times.

Artificial neural networks (ANNs) and spiking neural networks (SNNs) are two general approaches to achieve artificial intelligence (AI). The former have been widely used in academia and industry fields; the latter, SNNs, are more similar to biological neural networks and can realize ultra-low power consumption, thus have received widespread research attention. However, due to their fundamental differences in computation formula and information coding, the two methods often require different and incompatible platforms. Alongside the development of AI, a general platform that can support both ANNs and SNNs is necessary. Moreover, there are some similarities between ANNs and SNNs, which leaves room to deploy different networks on the same architecture. However, there is little related research on this topic. Accordingly, this article presents an energy-efficient, scalable, and non-Von Neumann architecture (EPHA) for ANNs and SNNs. Our study combines device-, circuit-, architecture-, and algorithm-level innovations to achieve a parallel architecture with ultra-low power consumption. We use the compensated ferrimagnet to act as both synapses and neurons to store weights and perform dot-product operations, respectively. Moreover, we propose a novel computing flow to reduce the operations across multiple crossbar arrays, which enables our design to conduct large and complex tasks. On a suite of ANN and SNN workloads, the EPHA is 1.6× more power-efficient than a state-of-the-art design, NEBULA, in the ANN mode. In the SNN mode, our design is 4 orders of magnitude more than the Loihi in power efficiency.

High-quality random numbers are very critical to many fields such as cryptography, finance, and scientific simulation, which calls for the design of reliable true random number generators (TRNGs). Limited by entropy source, throughput, reliability, and system integration, existing TRNG designs are difficult to be deployed in real computing systems to greatly accelerate target applications. This study proposes a TRNG circuit named resilient high-speed (RHS)-TRNG based on spin-transfer torque magnetic tunnel junction (STT-MTJ). RHS-TRNG generates resilient and high-speed random bit sequences exploiting the stochastic switching characteristics of STT-MTJ. By circuit/system codesign, we integrate RHS-TRNG into a reduced instruction set computer-V (RISC-V) processor as an acceleration component, which is driven by customized random number generation instructions. Our experimental results show that a single cell of RHS-TRNG has a random bit generation speed of up to 303 Mb/s, which is the highest among existing MTJ-based TRNGs. Higher throughput can be achieved by exploiting cell-level parallelism. RHS-TRNG also shows strong resilience against PVT variations thanks to our designs using bidirectional switching currents and dual generator units. In addition, our system evaluation results using gem5 simulator suggest that the system equipped with RHS-TRNG can achieve 3.4–$12\times $higher performance in speeding up option pricing programs than software implementations of random number generation.

Deadlock-free adaptive routing is extensively adopted in interconnection networks to improve communication bandwidth and reduce latency. However, existing deadlock-free flow control schemes either underutilize memory resources due to inefficient buffer management for simple hardware implementations, or rely on complicated coordination and synchronization mechanisms with high hardware complexity. In this work, we solve the deadlock problem from a different perspective by considering the deadlock as a lack of credit. With minor modifications of the credit accumulation procedure, our proposed full-credit flow control (FFC) ensures atomic buffer usage only based on local credit status while making full use of the buffer space. FFC can be easily integrated in the industrial router to achieve deadlock freedom with less area and power consumption, but 112% higher throughput, compared to the critical bubble scheme (CBS). We further propose a credit reservation strategy to eliminate the escape virtual channel (VC) cost for fully adaptive routing implementation. The synthesizing results demonstrate that FFC along with credit reservation (FFC-CR) can reduce the area by 29% and power consumption by 26% compared with CBS.

Compact convolutional neural networks have become a hot research topic. However, we find that the systolic array accelerators are extremely inefficient in dealing with compact models, especially when processing depthwise convolutional layers in the neural networks. To make systolic arrays more efficient for compact convolutional neural networks, we propose the heterogeneous systolic array (HeSA) architecture. It introduces heterogeneous processing elements that support multiple modes of dataflow, which can further exploit the reuse data chance of depthwise convolutional layers and without changing the scale or structure of the nave systolic array. By increasing the utilization rate of processing elements in the array, the HeSA improves the performance, throughput, and energy efficiency compared to the standard baseline. In addition, we design the flexible buffer structure for the communication between the computing array and external buffer. Through flexible routing, the HeSA can achieve a large-scale array design with maintaining high processing elements utilization rate and low communication costs. Based on our evaluation with typical workloads, the HeSA improves the utilization rate of the computing resource in depthwise convolutional layers by 4.5 - 11.2 and acquires 1.6 - 3.1 total performance speedup compared to the standard systolic array architecture. In the large-scale array design, the HeSA can reduce the data traffic by 40% while maintaining the same performance as the scaling-out method. By improving the on-chip data reuse chance and reducing data traffic, the HeSA saves over 20% in energy consumption. Meanwhile, the area of the HeSA is basically unchanged compared to the baseline due to its simple design.

Compact convolutional neural networks have become a hot research topic. However, we find that the hardware accelerator with systolic arrays processing compact models is extremely performance-inefficient, especially when processing depthwise convolutional layers in the networks. To make systolic arrays efficient for compact convolutional neural networks, we propose the heterogeneous systolic array (HeSA) architecture. It introduces heterogeneous processing elements that support multiple modes of dataflow, which can further exploit the reuse data chance of depthwise convolutional layers and without changing the architecture of the naïve systolic array. By increasing the utilization rate of processing elements in the array, HeSA improves the performance, throughput, and energy efficiency compared to the standard baseline. Based on our evaluation with typical workloads, HeSA improves the utilization rate of the computing resource in depthwise convolutional layers by 4.5×-5.5× and acquires 1.5-2.2× total performance speedup compared to the standard systolic array architecture. HeSA also improves the on-chip data reuse chance and saves over 20% of energy consumption. Meanwhile, the area of HeSA is basically unchanged compared to the baseline due to its simple design.

The systolic array architecture is one of the most popular choices for convolutional neural network hardware accelerators. The biggest advantage of the systolic array architecture is its simple and efficient design principle. Without complicated control and dataflow, hardware accelerators with the systolic array can calculate traditional convolution very efficiently. However, this advantage also brings new challenges to the systolic array. When computing special types of convolution, such as the small-scale convolution or depthwise convolution, the processing element (PE) utilization rate of the array decreases sharply. The main reason is that the simple architecture design limits the flexibility of the systolic array. In this article, we design a configurable multi-directional systolic array (CMSA) to address these issues. First, we added a data path to the systolic array. It allows users to split the systolic array through configuration to speed up the calculation of small-scale convolution. Second, we redesigned the PE unit so that the array has multiple data transmission modes and dataflow strategies. This allows users to switch the dataflow of the PE array to speed up the calculation of depthwise convolution. In addition, unlike other works, we only make a few changes and modifications to the existing systolic array architecture. It avoids additional hardware overheads and can be easily deployed in application scenarios that require small systolic arrays such as mobile terminals. Based on our evaluation, CMSA can increase the PE utilization rate by up to 1.6 times compared to the typical systolic array when running the last layers of ResNet-18. When running depthwise convolution in MobileNet, CMSA can increase the utilization rate by up to 14.8 times. At the same time, CMSA and the traditional systolic arrays are similar in area and energy consumption.

The systolic array is one of the most popular choices for convolutional neural network accelerators. However, when computing special convolution, such as small-scale convolution or depthwise convolution, the utilization rate of the array fluctuates or even declines sharply. To address these issues, we design a configurable multi-directional systolic array (CMSA). The array can switch data mapping or dataflow for special convolution by changing the data transmission direction and configuring the array. Meanwhile, it keeps the original systolic array architecture and computing mode. Our design makes the systolic array flexible. Based on our evaluation, CMSA can increase the units utilization rate by up to 1.6× compared to the typical systolic array when running last layers of ResNet. When running depthwise convolution in MobileNet, CMSA can increase the utilization rate by up to 14.8×.

The demand for multitasking GPUs increases whenever the GPU may be shared by multiple applications, either spatially or temporally. This requires that GPUs can be preempted and switch context to a new application while already executing one. Unlike CPUs, context switching in GPUs is prohibitively expensive due to the large context states to swap out. There have been a number of efforts on reducing the overhead of preemption, through reducing the context sizes or overlapping context switching with execution. All those techniques are reactive approaches, meaning that context switching occurs when the preemption request arrives. In this paper, we propose a dynamic and proactive mechanism to reduce the latency of preemption. We observe that kernel execution is almost always preceded by known commands in both CUDA and OpenCL implementations. Hence, a preemption can be anticipated before the actual request arrives. We study such lead time and develop a prediction scheme to perform an early state saving. When the actual preemption is invoked, an incremental update relative to the previous saved state is performed, much like the conventional checkpointing mechanism. Our design can also choose to drain or checkpointing dynamically and accurately according to the feature of kernels in the runtime. This design effectively reduces the stall time of the preempting kernel due to context switching by 58.6%. Moreover, through careful handling of the saved state, we can also reduce the overall size of saved state by an average of 23.3%, compared with a full context switching.

In this paper, we address the problem of how to achieve energy-efficient confined-interference communication on a bufferless NoC taking advantage of the low power consumption of such NoC. We propose a novel routing approach called Surfing on a Bufferless NoC (Surf-Bless) where packets are assigned to domains and Surf-Bless guarantees that interference between packets is confined within a domain, i.e., there is no interference between packets assigned to different domains. By experiments, we show that our Surf-Bless routing approach is effective in supporting confined-interference communication and consumes much less energy than the related approaches.

The parallelization of matrix multiplication on multicore accelerators divides a matrix into several partitions. The existing design deploys an independent DMA transfer for each core to access its own partition from DRAM. This design has poor memory access efficiency, since memory access streams of multiple concurrent DMA transfers interfere with each other. We propose Distributed-DMA (D-DMA), which invokes one transfer to serve all cores. D-DMA accesses data in a row-major manner to efficiently exploit inter-partition locality to improve the DRAM access efficiency. Compared with a baseline design, D-DMA improves the bandwidth by 84.8% and reduces DRAM energy consumption by 43.1% for micro-benchmarks. It achieves higher performance for the GEMM benchmark. With much lower hardware cost, D-DMA significantly outperforms an out-of-order memory controller.

High power consumption becomes the major bottleneck that prevents applying Network-on-Chips (NoCs) on future many-core systems. Power gating is an effective way to reduce the power consumption of a NoC. However, conventional power gating approaches cause significant packet latency increase as well as additional power consumption overhead due to the power gating mechanism. One comprehensive way to reduce these negative impacts is to bypass powered-off routers in a NoC when transferring packets. Therefore, in this paper, we propose an express virtual channel based (EVC-based) power gating approach. In our approach, packets can take pre-defined virtual bypass paths to bypass intermediate routers that can be powered-on or powered-off. Furthermore, based on our extended router structure, a certain transmission ability of the powered-off routers is kept to transfer packets going through the normal paths. Thus, even though some packets do not take a virtual bypass path, they still have less probability to be blocked by the powered-off routers. Compared with a conventional NoC without power gating, our EVC-based power gating approach causes only 2.67% performance penalty, which is less than 28.67%, 7.24%, and 5.69% penalties in related approaches. With small hardware overhead, our approach reduces on average 68.29% of the total power consumption in a NoC, which is comparable with the 72.94%, 73.56%, and 75.3% reduction of the total power consumption in related approaches.

We design an efficient DMA controller for scientific computing accelerators. It supports several flexible and powerful transfers, including reshape transfers, parameter linking mechanism, and transfer chaining meachnism. We also optimize the DMA controller for critical scientific computing kernels. It supports high bandwidth matrix transposition during data movement. It improves the memory access efficiency for matrix multiplication. Experimental results show that the data movement bandwidth achieved by the DMA controller is similar to the theoretical maximum one. It also performs very closely to an ideal design for real applications.

Modern GPUs feature an increasing number of streaming multiprocessors (SMs) to boost system throughput. How to construct an efficient and scalable network-on-chip (NoC) for future high-performance GPUs is particularly critical. Although a mesh network is a widely used NoC topology in manycore CPUs for scalability and simplicity reasons, it is ill-suited to GPUs because of the many-to-few-to-many traffic pattern observed in GPU-compute workloads. Although a crossbar NoC is a natural fit, it does not scale to large SM counts while operating at high frequency. In this paper, we propose the converge-diverge crossbar (CD-Xbar) network with round-robin routing and topology-aware concurrent thread array (CTA) scheduling. CD-Xbar consists of two types of crossbars, a local crossbar and a global crossbar. A local crossbar converges input ports from the SMs into so-called converged ports; the global crossbar diverges these converged ports to the last-level cache (LLC) slices and memory controllers. CD-Xbar provides routing path diversity through the converged ports. Round-robin routing and topology-aware CTA scheduling balance network traffic among the converged ports within a local crossbar and across crossbars, respectively. Compared to a mesh with the same bisection bandwidth, CD-Xbar reduces NoC active silicon area and power consumption by 52.5 and 48.5 percent, respectively, while at the same time improving performance by 13.9 percent on average. CD-Xbar performs within 2.9 percent of an idealized fully-connected crossbar. We further demonstrate CD-Xbar's scalability, flexibility and improved performance per Watt (by 17.1 percent) over state-of-the-art GPU NoCs which are highly customized and non-scalable.

High performance implementation of matrix multiplication is essential for scientific computing. The memory access procedure is quite possible to be the bottleneck of matrix multiplication. The widely used GotoBLAS GEMM implementation divides the integral matrix into several partitions to be assigned to different cores for parallelization. Traditionally, each core deploys a DMA transfer to access its own partition in the DRAM memory. However, deploying an independent DMA transfer for each core cannot efficiently exploit the inter-core locality. Also, multiple concurrent DMA transfers interfere with each other, further reducing the DRAM access efficiency. We observe that the same row of neighboring partitions is in the same DRAM page, which means that there is significant locality inherent in the address layout. We propose the coordinated DMA to efficiently exploit the locality. It invokes one transfer to serve all cores and moves data in a row-major manner to improve the DRAM access efficiency. Compared with a baseline design, the coordinated DMA improves the bandwidth by 84.8 percent and reduces DRAM energy consumption by 43.1 percent for micro-benchmarks. It achieves higher performance for the GEMM and Linpack benchmark. With much less hardware costs, the coordinated DMA significantly outperforms an out-of-order memory controller.

The design of efficient Networks-on-Chip (NoCs) is essential for GPGPUs. The asymmetry of GPGPU traffic has a significant effect on the overall system performance. An existing VC partitioning design statically assigns more VCs to the heavier reply traffic. Yet, its static partitioning cannot adapt to the dynamic variation of NoC traffic. Thus, we propose an adaptive VC partitioning (A-VCP) mechanism , which dynamically chooses the optimal VC partitioning by sampling the traffic status. Compared with the static configuration, A-VCP averagely improves the system performance by 10.5%, and reduces the energy-delay product by 9.1%.

Convolutional neural networks (CNNs) have a wide range of applications in image and video recognition, recommender systems and natural language processing. But CNNs are computationally intensive, and its computational cost is hard to accept. In order to speed up the calculations, people focus on optimizing convolution that account for most of the proportion of CNNs' operation. So, many algorithms have been proposed to accelerate the operation of convolution layers. However, each algorithm has its advantages and disadvantages, and there is no one algorithm that can handle all situations. In this paper, we examine the performance of various algorithms in GPU environment. By building a customized CNN model, we have fully explored the impact of the neural structure on the performance of algorithms, including inference/training speed, memory consumption and power consumption. In addition to the algorithms, we also focus on how their implementations in GPU environment affect their performance. We trace the kernel functions of these implementations to further generalize the characteristics of these algorithms. Finally, we summarize the characteristics of each algorithm., and design a strategy to assigns the appropriate implementation for different convolutional layers in CNNs. With our strategy, we can make AlexNet run 1.2× to 2.8× faster than other strategies in GPU environment. This work has very important meaning for understanding these algorithms and may provide insights for further optimizations of the architecture of GPUs and accelerators.

Genomic islands (GIs) that are associated with microbial adaptations and carry sequence patterns different from that of the host are sporadically distributed among closely related species. This bias can dominate the signal of interest in GI detection. However, variations still exist among the segments of the host, although no uniform standard exists regarding the best methods of discriminating GIs from the rest of the genome in terms of compositional bias. In the present work, we proposed a robust software, MTGIpick, which used regions with pattern bias showing multiscale difference levels to identify GIs from the host. MTGIpick can identify GIs from a single genome without annotated information of genomes or prior knowledge from other data sets. When real biological data were used, MTGIpick demonstrated better performance than existing methods, as well as revealed potential GIs with accurate sizes missed by existing methods because of a uniform standard. Software and supplementary are freely available at http://bioinfo.zstu.edu.cn/MTGI or https://github.com/bioinfo0706/MTGIpick.

Aggressive scaling of CMOS process technology allows the fabrication of highly integrated chips, and enables the design of multiprocessors system-on-chip connected by the network-on-chip (NoC). However, it brings about widespread reliability challenges. Aiming to tackle the permanent faults on the router components, we propose a high performance, high reliability and low cost router design based on a generic 2-stage router. Four fault tolerant strategies are added in our reliable router. We exploit a double routing strategy for the routing computation(RC) failure, a default winner strategy for the virtual channel allocation (VA), a runtime arbiter selection strategy for the switch allocation (SA) failure and a double bypass bus strategy for the crossbar failure. Different from previous reliable routers, our design leverages the feature of pipeline optimization and routing algorithm to maintain the performance in fault tolerance especially under heavy network loads. Besides, our proposed router provides higher reliability with lower hardware consumption than previous reliable router designs.

As integrated circuits are limited by hardware resources, reducing cost while maintaining the performance becomes especially important. In this article, we propose a conflict-free NoC (cfNoC) for the GPGPU request network. The cfNoC eliminates (i) conflicts among different columns by deploying an exclusive subnet for each column, and (ii) conflicts inside the same column by using a token-based mechanism. The elimination of conflicts allows cfNoC to exploit different subnet channel widths to maintain the performance while reducing cost. Compared with a baseline mesh with 1 VC, our work reduces request network area by 22.6% and power by 23.7%. With 2 VCs, cfNoC achieves more than 37.6% power reduction compared to the baseline and the checkboard placement/routing (CP) design. All these benefits do not cause any performance loss.

As the 3D stacking technology still faces several challenges, the 2.5D stacking technology gains better application prospects nowadays. With the silicon interposer, the 2.5D stacking can improve the bandwidth and capacity of the memory system. To satisfy the communication requirements of the integrated memory system, the free routing resources in the interposer should be explored to implement an additional network. Yet, the performance is strongly limited by the unbalanced loads between the CPU-layer network and the interposer-layer network. In this paper, to address this issue, we propose a dynamic latency-aware load-balancing (DLL) strategy. Our key innovations are detecting congestion of the network layer via the average latency of recent packets and making the network layer selection at each source node. We leverage the free routing resources in the interposer to implement a latency propagation ring. With the ring, the latency information tracked at destination nodes is propagated back to source nodes. We achieve load-balance by using these information. Experimental results show that compared with the baseline design, a destination-detection strategy and a buffer-aware strategy, our DLL strategy achieves 45%, 14.9% and 6.5% of average throughput improvements with minor overheads.

To achieve high throughput, core count in compute accelerators such as General-Purpose Graphics Processing Units (GPGPUs) increases continuously. The communication demand of these cores boosts the demand for a low-latency packet switched network. As packet latency is mainly composed of per-hop latency, contention latency and serialization latency, a favorable Network-on-Chip (NoC) design should efficiently decrease these three latency contributors to meet the communication demand while keeping hardware cost low. In this paper, we first make two observations about the NoC differences between CMPs and GPGPUs, and then design a Heterogeneous Ring-Chain network (HRCnet) for the GPGPU reply network. HRCnet eliminates conflicts in the network by proposing a ring-similar topology, using a novel node placement and introducing unidirectional channels. Eliminating conflicts reduces the per-hop latency and removes the contention latency, and exploiting the ring-similar topology reduces the serialization latency. Experimental results show the benefits of the low-cost low-latency design. With the same bisection bandwidth compared to the baseline mesh, our work yields a 45% performance improvement while reducing the area by 42% and reducing energy consumption by 60%. Compared to two state-of-the-art GPGPU NoCs, BENoC and DA2mesh, HRCnet achieves more than 42% performance gain at reduced hardware cost. Our work also achieves the highest power and area efficiency among the designs.

The sinking flux of particulate organic carbon (POC) from the surface ocean is a central driver of ocean biogeochemical cycling, which is directly related to the integrated NPP through euphotic layer. Using the global NPP data (estimated by remote sensing model) and other relevant satellite-derived data, the sinking flux of POC was derived following different algorithms. In situ data was used to compare the accuracy of these algorithms and the best algorithm was chosen to derive the global POC flux over period 2003~2012. Then, the estimated global POC flux data were applied to study the spatial and temporal distribution characteristic of POC flux. The average annual total global POC flux at the bottom of euphotic layer is about 9.7 Gt C for period of 2003~2012.

The interaction between packets affects performance and global fairness of Network-on-Chip. Preferentially transferring packets with small remaining hop counts (PPSR) can reduce the flying packet amount to improve the performance. Yet, the global fairness is negatively affected. In contrast, preferentially transferring packets with large remaining hop counts (PPLR) can achieve better global fairness with a poorer performance. In this paper, we propose adaptive remaining hop count flow control, which dynamically switches between PPSR and PPLR. In this way, we can achieve higher performance and better global fairness.

Short and long packets co-exist in cache-coherent NoCs. Existing designs for torus networks do not efficiently handle variable-size packets. For deadlock free operations, a design uses two VCs, which negatively affects the router frequency. Some optimizations use one VC. Yet, they regard all packets as maximum-length packets, inefficiently utilizing the precious buffers. We propose flit bubble flow control (FBFC), which maintains one free flit-size buffer slot to avoid deadlock. FBFC uses one VC, and does not treat short packets as long ones. It achieves both high frequency and efficient buffer utilization. FBFC performs 92.8 and 34.2 percent better than LBS and CBS for synthetic traffic in a$4 \times 4$torus. The gains increase in larger networks; they are 107.2 and 40.1 percent in an$8 \times 8$torus. FBFC achieves an average 13.0 percent speedup over LBS for PARSEC workloads. Our results also show that FBFC is more power efficient than LBS and CBS, and a torus with FBFC is more power efficient than a mesh.

Turn-model is a classical method for designing partially adaptive routing algorithms without virtual channels, and can also be the basis of fully adaptive routing algorithms. We propose a novel scheme, Selective Extension of Routing Algorithms based on turn model (SERA), which alleviates restrictions on turn and path selections if possible without adding any new buffers or virtual channels. SERA can improve adaptivity of the original routing algorithms, and maintain the deadlock-free property. Thus, SERA is an important extension of the previous turn model theory. To present the effectiveness of SERA in adaptive algorithms, we redesign two existing routing algorithms, Odd-Even and LEAR. Simulation results show that the SERA scheme achieves an average delay reduction of 6% compared to the original routing algorithms.

To provide efficient, high-performance routing algorithms, a holistic approach should be taken. The key aspects of routing algorithm design include adaptivity, path selection strategy, VC allocation, isolation, and hardware implementation cost; these design aspects are not independent. The key contribution of this work lies in the design of a novel selection strategy, Destination-Based Selection Strategy (DBSS), which targets interference that can arise in many-core systems running consolidation workloads. In the process of this design, we holistically consider all aspects to ensure an efficient design. Existing routing algorithms largely overlook issues associated with workload consolidation. Locally adaptive algorithms do not consider enough status information to avoid network congestion. Globally adaptive routing algorithms attack this issue by utilizing network status beyond neighboring nodes. However, they may suffer from interference, coupling the behavior of otherwise independent applications. To address these issues, DBSS leverages both local and nonlocal network status to provide more effective adaptivity. More importantly, by integrating the destination into the selection procedure, DBSS mitigates interference and offers dynamic isolation among applications. Results show that DBSS offers better performance than the best baseline selection strategy and improves the energy-delay product for medium and high injection rates; it is well suited for workload consolidation.

In this paper, an algorithm for estimating shallow-water depth from hyperspectral data is proposed. This methodology is based on the different responses of shallow-water reflectance on depth and substrate type. Two parameters-similarity coefficient and Pearson correlation coefficient-are introduced to describe the different types of responses, and a linear logarithm ratio model is established. Using Hyperion data over the coastal regions of O'Ahu Island and Saint Thomas Island, the retrieved bathymetry is compared with the airborne LIDAR data. The validation results show that the proposed method has good performance, and the root mean square error is less than 1.5 m over shallow water (shallower than 20 m).

Routing algorithms for cache-coherent NoCs only have limited VCs at their disposal, which poses challenges to the design of routing algorithms. Existing fully adaptive routing algorithms apply conservative VC re-allocation: only empty VCs can be re-allocated, which limits performance. We propose two novel flow control designs. First, whole packet forwarding (WPF) re-allocates a nonempty VC if the VC has enough free buffers for an entire packet. WPF does not induce deadlock if the routing algorithm is deadlock-free using conservative VC re-allocation. It is an important extension to several deadlock avoidance theories. Second, we extend Duato's theory to apply aggressive VC re-allocation on escape VCs without deadlock. Finally, we propose a design which maintains maximal routing flexibility with low hardware cost. For synthetic traffic, our design performs averagely 88.9 percent better than existing fully adaptive routing. Our design is superior to partially adaptive and deterministic routing.

In the current article, the capability and flexibility of field programmable gate-arrays (FPGAs) to implement IEEE-754 double-precision floating-point elementary functions are explored. To perform various elementary functions on the unified hardware efficiently, we propose a special-purpose very long instruction word (VLIW) processor, called DP_VELP. This processor is equipped with multiple basic units, and its performance is improved through an explicitly parallel technique. Pipelined evaluation of polynomial approximation with Estrin's scheme is proposed, by scheduling basic components in an optimal order to avoid data hazard stalls and achieve minimal latency. The custom VLIW processor can achieve high scalability. Under the control of specific VLIW instructions, the basic units are combined into special-purpose hardware for elementary functions. Common elementary functions are presented as examples to illustrate the design of elementary function in DP_VELP in detail. Minimax approximation scheme is used to reduce degree of polynomial. Compromise between the size of lookup table and the latency is discussed, and the internal precision is carefully planned to guarantee accuracy of the result. Finally, we create a prototype of the DP_VELP unit and an FPGA accelerator based on the DP_VELP unit on a Xilinx XC6VLX760 FPGA chip to implement the SGP4/SDP4 application. Compared with previous researches, the proposed design can achieve low latency with a reasonable amount of resources and evaluate a variety of elementary functions with the unified hardware to satisfy the demands in scientific applications. Experimental results show that the proposed design guarantees more than 99% of correct rounding. Moreover, the SGP4/SDP4 accelerator, which is equipped with 39 DP_VELP units and runs at 200 MHz, outperforms the parallel software approach with hyper-thread technology on an Intel Xeon Quad E5620 CPU at 2.40 GHz by a factor of 7X.

Across many architectures and parallel programming paradigms, collective communication plays a key role in performance and correctness. Hardware support is necessary to prevent important collective communication from becoming a system bottleneck. Support for multicast communication in Networks-on-Chip (NoCs) has achieved substantial throughput improvements and power savings. In this paper, we explore support for reduction or many-to-one communication operations. As a case study, we focus on acknowledgement messages (ACK) that must be collected in a directory protocol before a cache line may be upgraded to or installed in the modified state. This paper makes two primary contributions: an efficient framework to support the reduction of ACK packets and a novel Balanced, Adaptive Multicast (BAM) routing algorithm. The proposed message combination framework complements several multicast algorithms. By combining ACK packets during transmission, this framework not only reduces packet latency by 14.1% for low-to-medium network loads, but also improves the network saturation throughput by 9.6% with little overhead. The balanced buffer resource configuration of BAM improves the saturation throughput by an additional 13.8%. For the PARSEC benchmarks, our design offers an average speedup of 12.7% and a maximal speedup of 16.8%.

Routing algorithms for networks-on-chip (NoCs) typically only have a small number of virtual channels (VCs) at their disposal. Limited VCs pose several challenges to the design of fully adaptive routing algorithms. First, fully adaptive routing algorithms based on previous deadlock-avoidance theories require a conservative VC re-allocation scheme: a VC can only be re-allocated when it is empty, which limits performance. We propose a novel VC re-allocation scheme, whole packet forwarding (WPF), which allows a non-empty VC to be re-allocated. WPF leverages the observation that the majority of packets in NoCs are short. We prove that WPF does not induce deadlock if the routing algorithm is deadlock-free using conservative VC re-allocation. WPF is an important extension of previous deadlock-avoidance theories. Second, to efficiently utilize WPF in VC-limited networks, we design a novel fully adaptive routing algorithm which maintains packet adaptivity without significant hardware cost. Compared with conservative VC re-allocation, WPF achieves an average 88.9% saturation throughput improvement in synthetic traffic patterns and an average 21.3% and maximal 37.8% speedup for PARSEC applications with heavy network loads. Our design also offers higher performance than several partially adaptive and deterministic routing algorithms.

Binary64 arithmetic is rapidly becoming inadequate to cope with today's large-scale computations due to an accumulation of errors. Therefore, binary128 arithmetic is now required to increase the accuracy and reliability of these computations. At the same time, an obvious trend emerging in modern processors is to extend their instruction sets by allowing single instruction multiple data (SIMD) execution, which can significantly accelerate the data-parallel applications. To address the combined demands mentioned above, this paper presents the architecture of a low-cost binary128 floating-point fused multiply add (FMA) unit with SIMD support. The proposed FMA design can execute a binary128 FMA every other cycle with a latency of four cycles, or two binary64 FMAs fully pipelined with a latency of three cycles, or four binary32 FMAs fully pipelined with a latency of three cycles. We use two binary64 FMA units to support binary128 FMA which requires much less hardware than a fully pipelined binary128 FMA. The presented binary128 FMA design uses both segmentation and iteration hardware vectorization methods to trade off performance, such as throughput and latency, against area and power. Compared with a standard binary128 FMA implementation, the proposed FMA design has 30 percent less area and 29 percent less dynamic power dissipation.

With the emergence of many-core architectures, it is quite likely that multiple applications will run concurrently on a system. Existing locally and globally adaptive routing algorithms largely overlook issues associated with workload consolidation. The shortsightedness of locally adaptive routing algorithms limits performance due to poor network congestion avoidance. Globally adaptive routing algorithms attack this issue by introducing a congestion propagation network to obtain network status information beyond neighboring nodes. However, they may suffer from intra- and inter-application interference during output port selection for consolidated workloads, coupling the behavior of otherwise independent applications and negatively affecting performance.

SIMD devices have gained widespread acceptance in modern microprocessor designs for their superior performance for multimedia applications. However, there are three remaining limitations to the efficient utilization of SIMD devices in general-purpose computer systems: memory alignment, data reorganization and control flow. This paper presents SIF, an efficient SIMD interface framework that addresses these three shortcomings without modifying existing ISA. It is designed around a permutation vector register file (PVRF) and it adds new extended instructions to set internal permutation state in SIMD datapath rather than putting the permutation state setting bits in every instruction. The implicit permutation capability provided by PVRF results in zero overhead, which frees the handling of three limitations by using permutation instructions. To further reduce the state setting instructions in SIMD datapath, a technique that moves the workloads from SIMD pipeline into scalar pipeline is also introduced. With the help of proposed compilation algorithm, SIF can efficiently transform regular SIMD codes into SIF codes which make it easily integrated in all existing SIMD devices. We implemented these techniques in a vectorizing compiler and experimental results show that most of the permutation overhead instructions can be eliminated and distinct performance speedup can be achieved, which is 37% higher than current SIMD techniques on average.

With advancement in science and technology, computing systems are becoming increasingly more complex with a growing number of heterogeneous software and hardware components. They are thus becoming more difficult to monitor, manage, and maintain. Traditional approaches to system management have been largely based on domain experts through a knowledge acquisition solution that translates domain knowledge into operating rules and policies. This process has been well known as cumbersome, labor intensive, and error prone. In addition, traditional approaches for system management are difficult to keep up with the rapidly changing environments. There is a pressing need for automatic and efficient approaches to monitor and manage complex computing systems. In this paper, we propose an integrated data-driven framework for computing system management by acquiring the needed knowledge automatically from a large amount of historical log data. Specifically, we apply text mining techniques to automatically categorize the log messages into a set of canonical categories, incorporate temporal information to improve categorization performance, develop temporal mining techniques to discover the relationships between different events, and take a novel approach called event summarization to provide a concise interpretation of the temporal patterns.

As a free application programming interface (API) for hardware-accelerated two-dimensional vector and raster graphics, OpenVG is becoming the standard for hardware development. This paper firstly proposes several optimization methods for OpenVG implementation, such as loop unrolling, operation transformation, function in lining, vectorization and address assignment, based on the hardware architecture and programming model of the Synchronous Data Triggered Architecture (SDTA). We then optimally realize the OpenVG path and paint algorithms on the SDTA with the direction of these methods and consideration of the algorithmspsila characteristics. The analysis results show that the optimized OpenVG algorithms achieved 3-9 times speedups compared with original ones.

Recently, there has been considerable interest in efficiently computing strongly correlated pairs in large databases. Most previous studies require the specification of a minimum correlation threshold to perform the computation. However, it may be difficult for users to provide an appropriate threshold in practice because different data sets typically have different characteristics. To this end, in this paper, we propose an alternative task: finding the top-k strongly correlated pairs. Consequently, we identify a two-dimensional monotone property of an upper bound of ϕ correlation coefficient and develop an efficient algorithm, called TOP-COP, to exploit this property to effectively prune many pairs even without computing their correlation coefficients. Our experimental results show that TOP-COP can be an order of magnitude faster than alternative approaches for mining the top-k strongly correlated pairs. Finally, we show that the performance of the TOP-COP algorithm is tightly related to the degree of data dispersion. Indeed, the higher the degree of data dispersion, the larger the computational savings achieved by the TOP-COP algorithm.

In this paper, we propose to model time series from a new angle: state transition points. When fluctuation of values in a time series crosses a certain point, it may trigger state transition in the system, which may lead to abrupt changes in many other time series. The concept of state transition points is essential in understanding the behavior of the time series and the behavior of the system. The new measure is robust and is capable of discovering correlations that Pearson's coefficient cannot reveal. We propose efficient algorithms to identify state transition points and to compute correlation between two time series. We also introduce some triangular inequalities to efficiently find highly correlated time series among many time series.

A novel scheme for item-based recommendation is proposed in this paper. In our framework, the items are described by an undirected weighted graph Q = (V,epsiv). V is the node set which is identical to the item set, and epsiv is the edge set. Associate with each edge eij isin epsiv is a weight omegaij ges 0, which represents similarity between items i and j. Without the loss of generality, we assume that any user's ratings to the items should be sufficiently smooth with respect to the intrinsic structure of the items, i.e., a user should give similar ratings to similar items. A simple algorithm is presented to achieve such a smooth solution. Encouraging experimental results are provided to show the effectiveness of our method.

Recently, there has been considerable interest in computing strongly correlated pairs in large databases. Most previous studies require the specification of a minimum correlation threshold to perform the computation. However, it may be difficult for users to provide an appropriate threshold in practice, since different data sets typically have different characteristics. To this end, we propose an alternative task: mining the top-k strongly correlated pairs. In this paper, we identify a 2-D monotone property of an upper bound of Pearson's correlation coefficient and develop an efficient algorithm, called TOP-COP to exploit this property to effectively prune many pairs even without computing their correlation coefficients. Our experimental results show that the TOP-COP algorithm can be orders of magnitude faster than brute-force alternatives for mining the top-k strongly correlated pairs.

A common problem encountered in many application scenarios is how to represent some prior knowledge about a system in order to determine its true state as efficiently as possible. The information is typically in the form of tests, or questions about the system. Each test can potentially reduce our uncertainty about the system's state. The problem is to represent the information capturing the dependence between tests, their outcomes, and possible states in an efficiently navigable way to aid diagnosis. The most common such representation is a flowchart with leaf nodes corresponding to possible states, and non-leaf nodes corresponding to tests about the state. The problem with flowcharts is that they are notoriously difficult to maintain. Additional knowledge often has to be manually integrated as the system changes, making it impossible to keep track of all possible decision paths, let alone optimize the flow to maximize performance. We propose an efficient method for optimizing an existing flowchart based on a conversion to an auxiliary matrix representation. The main goal of the paper is show a synergy between the two representations in the hope that this will help practitioners choose a better strategy for their applications. We show that such a conversion suggests ways to improve both representations - ways that were not envisioned when using each representation alone. Finally, we show that the two representations are informationally equivalent in the sense that one can be transformed into the other so that if both are used as black-boxes, one would not be able to tell them apart, regardless of which state the system is in.

Business system management (BSM), or called business service management, has drawn tremendous attention in recent years. The emergence of the phenomenon is a natural development after system management practitioners realized that understanding the status of a particular IT resource is to comprehend only a small part of the big picture. To truly maximize the business value of IT investments, it is essential to know how resources affects the applications and business processes supported. Equally important is the capability to properly configure IT resource monitoring mechanism to allow system administrators to focus on critical resources with business significance. While much effort has been put into real-time monitoring and reporting mechanism, monitoring design of business systems received comparatively little attention. In this paper, we describe a data-driven approach for monitoring design for both service level and resource utilization.

Traditional approaches to system management have been largely based on domain experts through a knowledge acquisition process that translates domain knowledge into operating rules and policies. This has been well known and experienced as a cumbersome, labor intensive, and error prone process. In addition, this process is difficult to keep up with the rapidly changing environments. In this paper, we will describe our research efforts on establishing an integrated framework for mining system log files for automatic management. In particular, we apply text mining techniques to categorize messages in log files into common situations, improve categorization accuracy by considering the temporal characteristics of log messages, develop temporal mining techniques to discover the relationships between different events, and utilize visualization tools to evaluate and validate the interesting temporal patterns for system management.

Irregularly observed time series and their analysis are fundamental for any application in which data are collected in a distributed or asynchronous manor. We propose a theoretical framework for analyzing both stationary and non-stationary irregularly spaced time series. Our models can be viewed as extensions of the well known autoregression (AR) model. We provide experiments suggesting that, in practice, the proposed approach performs well in computing the basic statistics and doing prediction. We also develop a resampling strategy that uses the proposed models to reduce irregular time series to regular time series. This enables us to take advantage of the vast number of approaches developed for analyzing regular time series.

Real-time problem diagnosis in large distributed computer systems and networks is a challenging task that requires fast and accurate inferences from potentially huge data volumes. In this paper, we propose a cost-efficient, adaptive diagnostic technique called active probing. Probes are end-to-end test transactions that collect information about the performance of a distributed system. Active probing uses probabilistic reasoning techniques combined with information-theoretic approach, and allows a fast online inference about the current system state via active selection of only a small number of most-informative tests. We demonstrate empirically that the active probing scheme greatly reduces both the number of probes (from 60% to 75% in most of our real-life applications), and the time needed for localizing the problem when compared with nonadaptive (preplanned) probing schemes. We also provide some theoretical results on the complexity of probe selection, and the effect of "noisy" probes on the accuracy of diagnosis. Finally, we discuss how to model the system's dynamics using dynamic Bayesian networks (DBNs), and an efficient approximate approach called sequential multifault; empirical results demonstrate clear advantage of such approaches over "static" techniques that do not handle system's changes.

Many problems can be reduced to the problem of combining multiple clusterings. In this paper, we first summarize different application scenarios of combining multiple clusterings and provide a new perspective of viewing the problem as a categorical clustering problem. We then show the connections between various consensus and clustering criteria and discuss the complexity results of the problem. Finally we propose a new method to determine the final clustering. Experiments on kinship terms and clustering popular music from heterogeneous feature sets show the effectiveness of combining multiple clusterings.

This paper proposes algorithms for discovering temporal patterns without predefined time windows. The problem of discovering temporal patterns is divided into two sub-tasks: (1) using "cheap statistics" for dependence testing and candidates removal, (2) identifying the temporal relationships between dependent event types. The dependence problem is formulated as the problem of comparing two probability distributions and is solved using a technique reminiscent of the distance methods used in spatial point process, while the latter problem is solved using an approach based on chi-squared tests. Experiments are conducted to evaluate the effectiveness and scalability of the proposed methods.

Entropy-type measures for the heterogeneity of clusters have been used for a long time. This paper studies the entropy-based criterion in clustering categorical data. It first shows that the entropy-based criterion can be derived in the formal framework of probabilistic clustering models and establishes the connection between the criterion and the approach based on dissimilarity co-efficients. An iterative Monte-Carlo procedure is then presented to search for the partitions minimizing the criterion. Experiments are conducted to show the effectiveness of the proposed procedure.

We describe algorithms and an architecture for a real-time problem determination system that uses online selection of most-informative measurements - the approach called herein active probing. Probes are end-to-end test transactions which gather information about system components. Active probing allows probes to be selected and sent on-demand, in response to one's belief about the state of the system. At each step the most informative next probe is computed and sent. As probe results are received, belief about the system state is updated using probabilistic inference. This process continues until the problem is diagnosed. We demonstrate through both analysis and simulation that the active probing scheme greatly reduces both the number of probes and the time needed for localizing the problem when compared with non-active probing schemes.

Clustering suffers from the curse of dimensionality, and similarity functions that use all input features with equal relevance may not be effective. We introduce an algorithm that discovers clusters in subspaces spanned by different combinations of dimensions via local weightings of features. This approach avoids the risk of loss of information encountered in global dimensionality reduction techniques, and does not assume any data distribution model. Our method associates to each cluster a weight vector, whose values capture the relevance of features within the corresponding cluster. We experimentally demonstrate the gain in perfomance our method achieves, using both synthetic and real data sets. In particular, our results show the feasibility of the proposed technique to perform simultaneous clustering of genes and conditions in microarray data.

In this paper, we propose a new clustering algorithm, IFD1, based on a cluster model of data coefficients D and feature coefficients F. The coefficients denote the degree (or weights) of the data and features associated with the clusters. Clustering is performed via an iterative optimization procedure to mutually reinforce the relationships between the coefficients. The mutually reinforcing optimization exploits the duality of the data and features and enable a simultaneous clustering of both data and features. We have shown the convergence property of the clustering algorithm and discussed its connections with various existential approaches. Extensive experimental results on both synthetic and real data sets show the effectiveness of IFD algorithm.

Document clustering has long been an important problem in information retrieval. In this paper, we present a new clustering algorithm ASI1 , which uses explicitly modeling of the subspace structure associated with each cluster. ASI simultaneously performs data reduction and subspace identification via an iterative alternating optimization procedure. Motivated from the optimization procedure, we then provide a novel method to determine the number of clusters. We also discuss the connections of ASI with various existential clustering approaches. Finally, extensive experimental results on real data sets show the effectiveness of ASI algorithm.

Inductive learning searches an optimal hypothesis that minimizes a given loss function. It is usually assumed that the simplest hypothesis that fits the data is the best approximate to an optimal hypothesis. Since finding the simplest hypothesis is NP-hard for most representations, we generally employ various heuristics to search its closest match. Computing these heuristics incurs significant cost, making learning inefficient and unscalable for large dataset. At the same time, it is still questionable if the simplest hypothesis is indeed the closest approximate to the optimal model. Recent success of combining multiple models, such as bagging, boosting and meta-learning, has greatly improved the accuracy of the simplest hypothesis, providing a strong argument against the optimality of the simplest hypothesis. However, computing these combined hypotheses incurs significantly higher cost. We first advert that as long as the error of a hypothesis on each example is within a range dictated by a given loss function, it can still be optimal. Contrary to common beliefs, we propose a completely random decision tree algorithm that achieves much higher accuracy than the single best hypothesis and is comparable to boosted or bagged multiple best hypotheses. The advantage of multiple random tree is its training efficiency as well as minimal memory requirement.

Event management is a focal point in building and maintaining high quality information infrastructures. We have witnessed the shift of the paradigm of event management in practice from root cause analysis (RCA) to action-oriented analysis (AOA). IBM has developed a pioneer event management methodology (EMD) based on the AOA paradigm and applied it to more than two hundred production sites with success. Foreseeably, more and more event management professionals will apply AOA in different incarnations in building proactive management facilities. By that, building correct and effective Event Relationship Networks (ERNs) becomes the dominating activity in AOA service design process. Currently, the quality of ERNs and the cost of building them largely depend on the knowledge of domain experts. We believe that we can utilize historical event logs in shortening the ERNs design process and perfecting the quality of ERNs. In this paper, we describe in detail how to apply this data-driven approach in ERN validation, completion and construction.

As the complexity of distributed computing systems increases, systems management tasks require significantly higher levels of automation; examples include diagnosis and prediction based on real-time streams of computer events, setting alarms, and performing continuous monitoring. The core of autonomic computing, a recently proposed initiative towards next-generation IT-systems capable of 'self-healing', is the ability to analyze data in real-time and to predict potential problems. The goal is to avoid catastrophic failures through prompt execution of remedial actions.This paper describes an attempt to build a proactive prediction and control system for large clusters. We collected event logs containing various system reliability, availability and serviceability (RAS) events, and system activity reports (SARs) from a 350-node cluster system for a period of one year. The 'raw' system health measurements contain a great deal of redundant event data, which is either repetitive in nature or misaligned with respect to time. We applied a filtering technique and modeled the data into a set of primary and derived variables. These variables used probabilistic networks for establishing event correlations through prediction algorithms. We also evaluated the role of time-series methods, rule-based classification algorithms and Bayesian network models in event prediction.Based on historical data, our results suggest that it is feasible to predict system performance parameters (SARs) with a high degree of accuracy using time-series models. Rule-based classification techniques can be used to extract machine-event signatures to predict critical events with up to 70% accuracy.

Exploring large data sets typically involves activities that iterate between data selection and data analysis, in which insights obtained from analysis result in new data selection. Further, data analysis needs to use a combination of analysis techniques: data summarization, mining algorithms and visualization. This interweaving of functions arises both from the semantics of what the analyst hopes to achieve and from scalability requirements for dealing with large data volumes. We refer to such a process as a progressive analysis. Herein is described a tool, Event Miner, that integrates data selection, mining and visualization for progressive analysis of temporal, categorical data. We discuss a data model and architecture. We illustrate how our tool can be used for complex mining tasks such as finding patterns not occurring on Monday. Further, we discuss the novel visualization employed, such as visualizing categorical data and the results of data mining. Also, we discuss the extension of the existing mining framework needed to mine temporal events with multiple attributes. Throughout, we illustrate the capabilities of Event Miner by applying it to event data from large computer networks.

There has been a growing interest in mining frequent itemsets in relational data with multiple attributes. A key step in this approach is to select a set of attributes that group data into transactions and a separate set of attributes that labels data into items. Unsupervised and unrestricted mining, however is stymied by the combinatorial complexity and the quantity of patterns as the number of attributes grows. In this paper we focus on leveraging the semantics of the underlying data for mining frequent itemsets. For instance, there are usually taxonomies in the data schema and functional dependencies among the attributes. Domain knowledge and user preferences often have the potential to significantly reduce the exponentially growing mining space. These observations motivate the design of a user-directed data mining framework that allows such domain knowledge to guide the mining process and control the mining strategy. We show examples of tremendous reduction in computation by using domain knowledge in mining relational data with multiple attributes.

Temporal data mining aims at finding patterns in historical data. Our work proposes an approach to extract temporal patterns from data to predict the occurrence of target events, such as computer attacks on host networks, or fraudulent transactions in financial institutions. Our problem formulation exhibits two major challenges: 1) we assume events being characterized by categorical features and displaying uneven inter-arrival times; such an assumption falls outside the scope of classical time-series analysis, 2) we assume target events are highly infrequent; predictive techniques must deal with the class-imbalance problem. We propose an efficient algorithm that tackles the challenges above by transforming the event prediction problem into a search for all frequent eventsets preceding target events. The class imbalance problem is overcome by a search for patterns on the minority class exclusively; the discrimination power of patterns is then validated against other classes. Patterns are then combined into a rule-based model for prediction. Our experimental analysis indicates the types of event sequences where target events can be accurately predicted.

Association rule mining aims at discovering patterns whose support is beyond a given threshold. Mining patterns composed of items described by an arbitrary subset of attributes in a large relational table represents a new challenge and has various practical applications, including the event management systems that motivated this work. The attribute combinations that define the items in a pattern provide the structural information of the pattern. Current association algorithms do not make full use of the structural information of the patterns: the information is either lost after it is encoded with attribute values, or is constrained by a given hierarchy or taxonomy. Pattern structures convey important knowledge about the patterns. We present an architecture that organizes the mining space based on pattern structures. By exploiting the interrelationships among pattern structures, execution times for mining can be reduced significantly. This advantage is demonstrated by our experiments using both synthetic and real-life datasets.

1 Introduction As it becomes feasible to collect large volumes of data, businesses are increasingly looking for ways to capitalize on these data, especially market data. To date, the focus has been frequent patterns, especially frequent association rules. However, in applications such as detecting anomalies in computer networks and identifying security intrusions, there is much more interest in patterns that predict undesirable situations, such as service disruptions. Such patterns are often infrequent (at least in well managed systems) and are characterized by statistical dependency rather than their frequency. Unfortunately, the statistical dependency based on the dependency test yields neither upward nor downward closure, and hence efficient algorithms cannot be constructed. Herein, we circumvent this problem by proposing fully dependent patterns, d-patterns. D-patterns are defined so as to ensure downward closure, which makes it possible for us to construct an efficient algorithm for their discovery. We apply our algorithm to data from a network at a large insurance company and show that several patterns of interest are discovered[8]. For example, a group of hosts generated port-scan events three times in a week. This provides a possible indicator of a security intrusion. In another example, we observed three events: network interface card failure, unreachable destination, and “cold start” trap often occurred together, although not frequent. The last event indicates that the router has failed and restarted. Then, the first two events may provide advance warning of when the third will occur.

In some domains, such as isolating problems in computer networks and discovering stock market irregularities, there is more interest in patterns consisting of infrequent, but highly correlated items rather than patterns that occur frequently (as defined by minsup, the minimum support level). We describe m-pattern, a new pattern that is defined in terms of minp, the minimum probability of mutual dependence of items in the pattern. We show that all infrequent m-pattern can be discovered by an efficient algorithm that makes use of: (1) a linear algorithm to qualify an m-pattern; (2) an effective technique for candidate pruning based on a necessary condition for the presence of an m-pattern; and (3) a level-wise search for m-pattern discovery (which is possible because m-patterns are downward closed). Further, we consider frequent m-patterns, which are defined in terms of both minp and minsup. Using synthetic data, we study the scalability of our algorithm. Then, we apply our algorithm to data from a production computer network both to show the m-patterns present and to contrast with frequent patterns. We show that when minp=0, our algorithm is equivalent to finding frequent patterns. However, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated itemsets. To date, many actionable m-patterns have been discovered in production systems.

Periodic behavior is common in real-world applications. However in many cases, periodicities are partial in that they are present only intermittently. The authors study such intermittent patterns, which they refer to as p-patterns. The formulation of p-patterns takes into account imprecise time information (e.g., due to unsynchronized clocks in distributed environments), noisy data (e.g., due to extraneous events), and shifts in phase and/or periods. We structure mining for p-patterns as two sub-tasks: (1) finding the periods of p-patterns and (2) mining temporal associations. For (2), a level-wise algorithm is used. For (1), we develop a novel approach based on a chi-squared test, and study its performance in the presence of noise. Further we develop two algorithms for mining p-patterns based on the order in which the aforementioned sub-tasks are performed: the period-first algorithm and the association-first algorithm. Our results show that the association-first algorithm has a higher tolerance to noise; the period-first algorithm is more computationally efficient and provides flexibility as to the specification of support levels. In addition, we apply the period-first algorithm to mining data collected from two production computer networks, a process that led to several actionable insights.

In some domains, such as isolating problems in computer networks and discovering stock market irregularities, there is more interest in patterns consisting of infrequent, but highly correlated items rather than patterns that occur frequently (as defined by minsup, the minimum support level). We describe the m-pattern, a new pattern that is defined in terms of minp, the minimum probability of mutual dependence of items in the pattern. We show that all infrequent m-patterns can be discovered by an efficient algorithm that makes use of: (a) a linear algorithm to qualify an m-pattern; (b) an effective technique for candidate pruning based on a necessary condition for the presence of an m-pattern; and (c) a level-wise search for m-pattern discovery (which is possible because m-patterns are downward closed). Further, we consider frequent m-patterns, which are defined in terms of both minp and minsup. Using synthetic data, we study the scalability of our algorithm. Then, we apply our algorithm to data from a production computer network both to show the m-patterns present and to contrast with frequent patterns. We show that when minp=0, our algorithm is equivalent to finding frequent patterns. However, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated itemsets. To date, many actionable m-patterns have been discovered in production systems.

Mining for frequent itemsets typically involves a preprocessing step in which data with multiple attributes are grouped into transactions, and items are defined based on attribute values. We hake observed that such fixed attribute mining can severely constrain the patterns that are discovered. Herein, we introduce mining spaces, a new framework for mining multi-attribute data that includes the discovery of transaction and item definitions (with the exploitation of taxonomies and functional dependencies if they are available). We prove that special downward closure properties (or anti-monotonic property) hold for mining spaces, a result that allows us to construct efficient algorithms for mining patterns without the constraints of fixed attribute mining. We apply our algorithms to real world data collected from a production computer network. The results show that by exploiting the special kinds of downward closure in mining spaces, execution times for mining can be reduced by a factor of three to four.

For large installations, event management is critical to ensuring service quality by responding rapidly to exceptional situations. The key to this is having experts encode their knowledge (e.g., in rules, state machines, codebooks) about the relationship between event patterns and actions to take. Unfortunately, doing so is time-consuming and knowledge-intensive. We propose reducing this burden by using offline decision support consisting of visualizing and mining event histories to discover patterns in event data. Our experience with a wide variety of production data has identified several patterns of interest such as, event bursts and partial periodicities. Herein, we use production data to illustrate how to visualize and mine event patterns, and we describe a tool we have developed to aid in pattern discovery.

An important issue in visualizing categorical data is how to order categorical values. The focus of this paper is on constructing such orderings efficiently without compromising their visual quality.

Heterogeneous network traffic possesses diverse statistical properties which include complex temporal correlation and non-Gaussian distributions. A challenge to modeling heterogeneous traffic is to develop a traffic model which can accurately characterize these statistical properties, which is computationally efficient, and which is feasible for analysis. This work develops wavelet traffic models for tackling these issues. We model the wavelet coefficients rather than the original traffic. Our approach is motivated by a discovery that although heterogeneous network traffic has the complicated short- and long-range temporal dependence, the corresponding wavelet coefficients are all "short-range" dependent. Therefore, a simple wavelet model may be able to accurately characterize complex network traffic. We first investigate what short-range dependence is important among the wavelet coefficients. We then develop the simplest wavelet model, i.e., the independent wavelet model for Gaussian traffic. We define and evaluate the (average) autocorrelation function and the buffer loss probability of the independent wavelet model for fractional Gaussian noise (FGN) traffic. This assesses the performance of the independent wavelet model, and the use of which for analysis. We also develop (low-order) Markov wavelet models to capture additional dependence among the wavelet coefficients. We show that an independent wavelet model is sufficiently accurate, and a Markov wavelet model only improves the performance marginally. We further extend the wavelet models to non-Gaussian traffic through developing a novel time-scale shaping algorithm. The algorithm is tested using real network traffic and shown to outperform FARIMA in both efficiency and accuracy. Specifically, the wavelet models are parsimonious, and have a computational complexity O(N) in developing a model from a training sequence of length N, and O(M) in generating a synthetic traffic trace of length M.

Cheng Ma and Chuanyi Ji (1998) and Chuanyi Ji et al. (1999) showed empirically that independent (Haar) wavelet models were parsimonious, computationally efficient and accurate in modeling heterogeneous network traffic measured by both auto-covariance functions and buffer loss rate. We also proved analytically that such models were capable of capturing any decay rate of auto-covariance functions at large lags. In this work, we focus on comparing independent (Haar) wavelet models against independent wavelet models with higher vanishing moments. It is shown that as the vanishing moments increase, the independent wavelet models have better performance in approximating the auto-covariance function at small lags. The computational cost for all independent wavelet models is O(N) for a trace of length N.

In our previous work, we showed empirically that independent wavelet models were parsimonious, computationally efficient, and accurate in modeling heterogeneous network traffic measured by both auto-covariance functions and buffer loss rate. In this work, we focus on auto-covariance functions, to establish a theory of independent wavelet models as unified models for heterogeneous network traffic. We have developed the theory on the approximation capability of independent wavelet models for heterogeneous traffic in terms of the decay rate of auto-covariance functions at large lags. Average auto-covariance functions of independent wavelet models have been derived and shown to be linear combinations of basis functions. Through a simple analytical expression, we have shown that the decay rate of the auto-covariance functions of independent wavelet models is determined explicitly through a single quantity called the rate function of variances of wavelet coefficients. By specifying analytical forms of the rate function, independent wavelet models have been shown as unified models of heterogeneous traffic in terms of auto-covariance functions. The simplicity of the theory thereby provides both quantitative and qualitative explanations why independent wavelet models are unified models of heterogeneous traffic.

This paper reviews recent advances in supervised learning with a focus on two most important issues: performance and efficiency. Performance addresses the generalization capability of a learning machine on randomly chosen samples that are not included in a training set. Efficiency deals with the complexity of a learning machine in both space and time. As these two issues are general to various learning machines and learning approaches, we focus on a special type of adaptive learning systems with a neural architecture. We discuss four types of learning approaches: training an individual model; combinations of several well-trained models; combinations of many weak models; and evolutionary computation of models. We explore advantages and weaknesses of each approach and their interrelations, and we pose open questions for possible future research.

We establish a wavelet model of video traffic. We model the wavelet coefficients in the wavelet domain, which is different from the existing methods which model the video traffic in the time domain. The strength of the wavelet model includes (1) a unified approach to model both the long-range and the short-range dependence in the video traffic simultaneously, (2) a computationally efficient method of developing the model and generating high quality video traffic, and (3) the feasibility of performance analysis using the model.

A significant discovery from this work is that although video traffic has complicated short- and long-range dependence in the time domain, the corresponding wavelet coefficients are no longer long-range dependent in the wavelet domain. Therefore, a "short-range" dependent process can be used to model video traffic in the wavelet domain. In this work, we develop such wavelet models for VBR video traffic. The strength of the developed wavelet models includes: (1) it provides a unified approach to model both long-range and short-range dependence in video traffic simultaneously, (2) it has the ability to reduce the temporal dependence so significantly that the wavelet coefficients can be modeled by either independent or Markov models, and (3) the model results in a computationally efficient method on generating high quality video traffic.

In this work, a probabilistic model is established for recurrent networks. The expectation-maximization (EM) algorithm is then applied to derive a new fast training algorithm for recurrent networks through mean-field approximation. This new algorithm converts training a complicated recurrent network into training an array of individual feedforward neurons. These neurons are then trained via a linear weighted regression algorithm. The training time has been improved by five to 15 times on benchmark problems.

To obtain classification systems with both good generalization performance and efficiency in space and time, we propose a learning method based on combinations of weak classifiers, where weak classifiers are linear classifiers (perceptrons) which can do a little better than making random guesses. A randomized algorithm is proposed to find the weak classifiers. They are then combined through a majority vote. As demonstrated through systematic experiments, the method developed is able to obtain combinations of weak classifiers with good generalization performance and a fast training time on a variety of test problems and real applications. Theoretical analysis on one of the test problems investigated in our experiments provides insights on when and why the proposed method works. In particular, when the strength of weak classifiers is properly chosen, combinations of weak classifiers can achieve a good generalization performance with polynomial space- and time-complexity.