The implementation of Network-on-Chip (NoC) architectures presents considerable advantages in performance relative to traditional bus-based systems. However, the sophisticated nature of NoC designs demands careful oversight of shared resources to mitigate potential performance issues. In this context, well-structured routing algorithms are essential, as they facilitate improved traffic management and minimize congestion. Furthermore, mechanisms for deadlock prevention and avoidance are integral to routing algorithms, ensuring continuous packet transmission and ultimately enhancing network performance. This paper introduces a novel reactive deadlock avoidance method for Triplet-Based Architecture Inter-Core NoC (TriBA-cNoC). that classifies routing based on Focus Routing Graph (FRG) size to address routing-level deadlocks caused by the combination of deterministic routing and TriBA-cNoC’s inherent network characteristics. Compared to proactive techniques, it improves downstream buffer utilization and reduces power consumption. Furthermore, two shortest-path routing algorithms are introduced: DM4T-M, which incorporates a round-robin selection mechanism to alleviate congestion on critical paths and minimize hot-node formation. TSR, a novel two-stage distributed routing algorithm, addresses the computational overhead associated with output port selection in previous algorithms. Simulation results obtained using gem5 show that the proposed approach, which integrates routing-level reactive deadlock avoidance with the proposed routing algorithms, yields improvements in latency, throughput, buffer utilization, and power consumption. TSR and DM4T-M achieve latency reductions of up to 34.89% and 28.2%, respectively. Throughput increases of up to 16.94% and 7.81% are observed for TSR and DM4T-M, respectively. Moreover, the proposed approaches enhance buffer utilization by up to 13.9% and 10.44%, while reducing power consumption by up to 9.64%.

Innovative processor architecture designs are shifting towards Many-Core Architectures (MCAs) to meet the future demands of high-performance computing as the limits of Moore’s Law have almost been reached. Many-core processors utilize shared memory hierarchies to achieve high-speed memory systems, improving memory access efficiency. However, as the number of cores multiplies, the scalability of this system is significantly constrained by the increased proportion of long-distance and Non-Uniform Memory Access (NUMA). Improving the scalability of MCAs is crucial for achieving large/super-scale general-purpose many-core processors. This work proposes a high-scalability memory Network-on-Chip (NoC) for Triplet-Based Many-Core Architecture (TriBA), named TriBA-mNoC. TriBA-mNoC maintains a consistent core-to-core spacing as the network scale increases, effectively preventing increased long-distance memory access latency. Moreover, it leverages an inherent advantage of shared-inside hierarchical-groupings, alleviating common NUMA issues in the NoC design. Evaluations of static network characteristics show that TriBA-mNoC outperforms most classical NoCs in network diameter, average distance, and cost. TriBA-mNoC can be integrated with TriBA in the same silicon die with a tile-like floorplan, forming a novel NoC called TriBA-NoC, which can combine the strengths of both networks to maximize the architecture performance. We evaluated the memory access performance and scalability of TriBA-NoC using the mathematical evaluation models and actual simulations with real traffic (PARSEC 3.0 and SPLASH-2) at different network scales. The mathematical evaluation results indicate that TriBA-NoC achieves an aggregate speedup of approximately 3x compared with 2D-Mesh for a similar number of cores. Furthermore, TriBA-NoC’s single-core speedup efficiency remains stable as the number of cores increases under the same cache hit ratio, whereas 2D-Mesh experiences a rapid decline, highlighting TriBA-NoC’s exceptional scalability. Finally, the actual traffic simulation results show that TriBA-NoC achieves an average memory access latency and time reduction of 25.90% to 40.50% and 5.61% to 31.69%, respectively, compared with 2D-Mesh.

Binary Sparse Matrix-Vector Multiplication (SpMV) is a heavy computational kernel in weblink analysis, integer factorization, compressed sensing, spectral graph theory, and other domains. Testing several popular GPU-based SpMV implementations on 400 sparse matrices, we observed that data transfer to GPU memory accounts for a large part of the total computation time. The transfer of constant value “1”s can be easily eliminated for binary sparse matrices. However, compressing index arrays has always been a great challenge. This article proposes a new compression format TaiChi to further reduce index data copies and improve the performance of SpMV, especially for diagonally dominant binary sparse matrices. Input matrices are first partitioned into relatively dense and ultra-sparse areas. Then the dense areas are encoded inversely by marking “0”s, while the ultra-sparse area is encoded by marking “1”s. We also designed a new SpMV algorithm only using addition and subtraction for binary matrices based on our partition and encoding format. Evaluation results on real-world binary sparse matrices show that our hybrid encoding for binary matrix significantly reduces the data transfer and speeds up the kernel execution. It achieves the highest transfer and kernel execution speedups of 5.63x and 3.84x on GTX 1080 Ti, 3.39x and 3.91x on Tesla V100.

SpMV is a cost-dominant operation used in many iterative methods for solving large-scale sparse linear systems. However, irregular memory access of SpMV to the multiplied vector leads to low data locality and then harms the performance. This paper presents an adaptive multi-row folding of CSR (AMF-CSR) format for SpMV calculation on GPU. This new storage format supports the folding of the variable number of rows in order to achieve better load balancing in computation. AMF-CSR not only increases the density of non-zero elements in a folded row, thereby improving the access locality of the multiplied vector, but also merges an approximately equal number of nonzero elements in a folded row, hence achieving load balancing. The performance evaluation using 28 sparse matrices shows that the proposed SpMV algorithm based on AMF-CSR achieves the highest speedup of 4.11x and 3.62x on GTX 1080 Ti and Tesla V100 respectively against a fixed multi-row folding-based SpMV algorithm. Evaluation results using 450 regular sparse matrices and 450 irregular sparse matrices also show that AMF-CSR is superior to other SpMV implementations.

The Sparse Matrix-Vector Multiplication (SpMV) kernel dominates the computing cost in numerous scientific applications. Many implementations based on different sparse formats were proposed to improve this kernel on the recent GPU architectures. However, it has been widely observed that there is no “best-for-all” sparse format for the SpMV kernel on GPU. Indeed, serious performance degradation of an order of magnitude can be observed without a careful selection of the sparse format to use. To address this problem, we propose in this article BestSF (Best Sparse Format), a new learning-based sparse meta-format that automatically selects the most appropriate sparse format for a given input matrix. To do so, BestSF relies on a cost-sensitive classification system trained using Weighted Support Vector Machines (WSVMs) to predict the best sparse format for each input sparse matrix. Our experimental results on two different NVIDIA GPU architectures using a large number of real-world sparse matrices show that BestSF achieved a noticeable overall performance improvement over using a single sparse format. While BestSF is trained to select the best sparse format in terms of performance (GFLOPS), our further experimental investigations revealed that using BestSF also led, in most of the test cases, to the best energy efficiency (MFLOPS/W). To prove its practical effectiveness, we also evaluate the performance and energy efficiency improvement achieved when using BestSF as a building block in a GPU-based Preconditioned Conjugate Gradient (PCG) iterative solver.

Sparse Matrix-Vector Multiplication (SpMV) kernel dominates the computing cost in numerous scientific applications. Many implementations based on different sparse formats were proposed recently for optimizing this kernel on the GPU side. Since the performance of the SpMV varies significantly according to the sparsity characteristics of the input matrix and the hardware features, developing an accurate performance model for this kernel is a challenging task. The traditional approach of building such models by analytical modeling is difficult in practice and requires a thorough understanding of the interaction between the GPU hardware and the sparse code. In this paper, we propose to use a machine learning approach to predict the performance of the SpMV kernel using several sparse formats (COO, CSR, ELL, and HYB) on GPU. We used two popular machine learning algorithms, Support Vector Regression (SVR) and Multilayer Perceptron neural network (MLP). Our experimental results on two different GPUs (Fermi GTX 512 and Maxwell GTX 980 Ti) show that the SVR models deliver the best accuracy with average prediction error ranging between 7% and 14%.

Sparse Matrix-Vector Multiplication (SpMV) kernel dominates the computing cost in numerous scientific applications. Many implementations based on different sparse formats were proposed recently for this kernel on the GPU side. Since the performance of these sparse formats varies significantly according to the sparsity characteristics of the input matrix and the hardware specifications, no one of them can be considered as the best one to use for every sparse matrix. In this paper, we address the problem of selecting the best representation for a given sparse matrix on GPU by using a machine learning approach. First, we present some interesting and easy to compute features for characterizing the sparse matrices on GPU. Second, we use a multiclass Support Vector Machine (SVM) classifier to select the best format for each input matrix. We consider in this paper four popular formats (COO, CSR, ELL, and HYB), but our work can be extended to support more sparse representations. Experimental results on two different GPUs (Fermi GTX 580 and Maxwell GTX 980 Ti) show that we achieved more than 98% of the performance possible with a perfect selection.

Fault tolerance and load balancing are critical points for executing long-running parallel applications on multicore clusters. This paper addresses both fault tolerance and load balancing on multicore clusters by presenting a novel work-stealing task scheduling framework which supports hardware fault tolerance. In this framework, both transient and permanent faults are detected and recovered at task granularity. We incorporate task-based fault detection and recovery mechanisms into a hierarchical work-stealing scheme to establish the framework. This framework provides low-overhead fault-tolerance and optimal load balancing by fully exploiting task parallelism.

Work-stealing has been widely used in task-based parallel programming for dynamic load balancing. The overhead of work-stealing on distributed memory systems is much higher than that on shared memory systems. To minimize the overhead of work-stealing on a multi-core cluster, we propose a hierarchical work-stealing framework, in which work-stealing is performed inside a node before across the node boundary. Two key techniques used in our framework to reduce the inter-node steals are: a) adaptive initial partitioning for different task parallel patterns; b) centralized control for inter-node work-stealing, which improves the efficiency of victim selection and termination detection. We compare our technique to the classical work-stealing scheme and a state-of-the-art work-stealing scheme [1] for multi-core clusters. Our technique outperforms them by 19% and 8% respectively.

Most CMPs use on-chip networks to connect cores and tend to integrate more simple cores on a single die. Low-radix networks, such as 2D-MESH, are widely used in tiled CMPs since they can be mapped to on-chip networks efficiently. However, low-radix networks introduce high network latency caused by long diameter. In this paper, we propose the use of group-caching design in NoC based multicore cache coherent systems. In our design, on-chip L2 banks are organized to form multiple groups. Each cache group behaves like a shared L2 cache for the cores inside cache group while the cache coherence between cache groups is maintained by coherence messages. Besides, group-caching also adopts the new cache replacement policy to improve the inefficient use of the aggregate L2 cache capacity. Compared to banked and shared L2 design, as most L2 accesses are served by local cache group, the hop count is significantly reduced. Experiment results based on full-system simulation show that for 2D-MESH, group-caching can increase the performance by 2%∼8% compared to banked and shared L2 design, with network energy consumption reduced by 11%∼13%. Experiment results also show that the communication overhead inside cache group plays an important role in the performance of groupcaching.

As current FPGAs grow in logic capacity, they are widely used to implement entire systems. In some specific applications, such as our embedded multi-core processor TriBA[1],user memory models are not limited to single-port or dual-port. Thus, we need a cost-effective way to realize N-port memory on FPGA since most commercial products do not provide N-port physical arrays. In this paper, we propose a hierarchical N-port memory architecture for LUT-based FPGAs. The principle of this architecture is to create a two-level memory hierarchy formed by different resources. We map the memory resources inside LUTs as 1-port memory banks, and interleave these banks to create N-port L1 memory. We also interleave physical dual-port arrays to build N-port L2 memory. We also provide the data transfer between L1 and L2 memories and assume that such data transfer is managed by software control just like the strategy used by SPM. Compared to L1 memory, L2 memory has the advantage in cost and also has several disadvantages, such as longer access time and higher conflict probability. If most accesses are served by its L1 memory portion, hierarchical memory architecture will achieve both goals in cost and access time. We implement this architecture on Xilinx Virtex-II chips to measure its cost and also use the memory trace collected from multi-core simulator to measure its average access time. The product of cost and average access time shows that, hierarchical memory architecture is a cost-effective way to realize N-port memory on FPGA.

As the computing ability of high performance computers are improved by increasing the number of computing elements, how to utilize the available computing resources becomes an important issue. Different strategies to solve an problem based on a multi-processing system can bring about distinct performance. In this paper, we propose a method to predict the performance of parallel applications. The method describes the parallel features of the multi-processing systems in a hierarchy way, and evaluates solutions based on the description. In this way, programmers can find the better solution of an application before real programming.

Scratchpad Memory (SPM) is a fast and small software-managed SRAM. Its current extensive uses in embedded processors are motivated by the advantages of power saving, small area and low access time compared with cache. However, existing SPM management methods depend heavily on profiling and compilers. The dependence on compiler also makes embedded applications hard to transplant. This paper presents a novel strategy to manage the scratchpad memory without compiler support. Based on the memory reference locality theory, a hardware random sampling module is adopted to dynamically identify the frequently accessed addresses at runtime. The consequential data movement and address redirection are handled by software operation with the assistance of memory management unit (MMU). We evaluate our method on 10 typical embedded applications and compare the results to a cache reference system. Experimental results show that, on average, our scheme can achieve 33:5% reduction in energy consumption with only slight (<1%) decrease in throughput versus the reference system.

A novel object-oriented processor is proposed in this paper, which provides support for object addressing, message passing and dynamic memory management. Object running on this processor has its own control thread and communicates with others via messages. A virtual addressed object cache that reduces the indirection overhead while maintaining the efficiency of object relocation is presented. Object table that maintains the handles is used to obtain the actual object location on an object cache miss. Hardware support for explicit dynamic memory management is provided. Object allocation and deletion is strictly bounded in time. Moreover, a new concurrently dynamic memory management algorithm is proposed, which enables the processor to freely access heap during memory compaction and the applications will not be suspended for the completion of memory compaction.

A real scalable triplet-based computer architecture TriBA is proposed in this paper. TriBA is an object-oriented chip multi-processor that supports truly parallel execution of objects from hardware. Cores on the same chip are connected via triplet-based hierarchical interconnection network (THIN), which has simple topology and computing locality characteristic. A distributed deterministic routing algorithm (DDRA) is elaborated, already proposed for THIN. Runtime objects are mapped to processor cores according to their coupling degree which can also transfer to idle cores if needed. TriBA achieves the unification of software architecture and computer, and also relieves the burden of parallel programming.

The memory intensive nature of object-oriented languages such as C++ and Java has created the need of a high-performance dynamic memory management (DMM); however, it is a challenging task to provide efficient reliable system without violating real time performance constraints. Hardware approach emerges as one of the candidate in improving the performance of DMM. This paper presents an efficient design for explicit dynamic memory management which exploits the high speed of a pure hardware implementation. Object allocation and deletion are strictly bounded in time. The whole heap space is divided into two semi-spaces, and a concurrent bidirectional memory compaction algorithm is proposed. So that memory compaction can be done while mutator process is running on the processor. A small built in object-based cache memory is available to avoid indirect object addressing inefficiencies. Experiments show that this hardware scheme can greatly improve the speed and predictability of DMM.

Hardware approach emerges as one of the candidate in improving the performance of dynamic memory management. This paper presents measurements of a self-maintained memory module subjected to several different workloads. This memory module supporting explicit dynamic memory management takes advantage of the high speed of a pure hardware implementation. Object allocation and deletion are strictly bounded in time. The whole heap space is divided into two semi-spaces, and a concurrent bidirectional memory compaction algorithm is exploited, so that memory compaction can be done while mutator process is running on the processor concurrently. Reported measurements demonstrate that hardware-assisted memory management is a viable alternative to traditional explicit memory management techniques. Experimental results show that more than 60% of memory traffic is saved by the proposed memory compaction scheme compared to software-only approach. Both processor delay and program execution time are greatly reduced.