Search

This paper presents parallel FFT algorithms with different degree of computation and communication overheads for multiprocessors in a Network-on-Chip (NoC) environment. Of the three parallel FFT algorithms presented in this paper, we propose two parallel FFT algorithms for a 2D NoC that can contain a variable number of processing elements (PEs) and one is a reference parallel FFT algorithm for comparison. A parallel FFT algorithm we propose increases performance by assigning well-balanced computation tasks to PEs. The execution times are reduced because the algorithm uses data locality well to avoid unnecessary data exchanges among PEs and removes the overall idle periods by2 a balanced task scheduling. An enhanced version of this algorithm is suggested in which communication traffic is reduced. In this algorithm, returning transformed data to an original PE after one computation stage before sending them to a next PE for the following stage is removed. Instead, we propose a method that enables to keep regularity of the data communication and computations with twiddle factors. According to the simulation result from our cycle-accurate SystemC NoC model with a parametrizable 2-D mesh architecture, and the analysis of the algorithms in time and complexity, our proposed algorithms are shown to outperform the reference parallel FFT algorithm and FFT implementations on TI Digital Signal Processors (DSPs) that have similar specifications to our simulation environment.

The computational performance of Network-on-Chip (NoC) and Multi-Processor System-on-Chip (MPSoC) for implementing cryptographic block ciphers can be improved by exploiting parallel and pipeline execution. In this paper, we present a parallel and pipeline processing method for block cipher algorithms: Data Encryption Standard (DES), Triple-DES Algorithm (TDEA), and Advanced Encryption Standard (AES) based on pure software implementation on an NoC. The algorithms are decomposed into task loops, functions, and data flow for parallel and pipeline execution. The tasks are allocated by the proposed mapping strategy to each Processing Element (PE) which consists of a 32-bit Reduced Instruction Set Computer (RISC) core, internal memory, router, and Network Interface (NI) to communicate between PEs.The proposed approach is simulated by using Networked Processor Array (NePA), the cycle-accurate SystemC and Hardware Description Language (HDL) model platform. We show that our method has the advantage of flexibility as compared to previous implementations of cryptographic algorithms based on hardware and software co-design or traditional hardwired ASIC design. In addition, the simulation result presents that the parallel and pipeline processing approach for software block ciphers can be implemented on various NoC platforms which have different complexities and constraints.

Many-cores are on the cusp of becoming state-of-the-art processor technology for the next decade. To guarantee efficient communication between multiple cores, a Network-on-a-Chip (NoC) is considered as an alternative to overcome the limitations of the ubiquitous bus technology.

This paper presents several parallel FFT algorithms with different degree of communication overhead for multiprocessors in network-on-chip (NoC) environment. Three different methods of parallel FFT are presented. One is the reference parallel FFT for comparison, and the other two with well-distributed computation as well as reduced communication overhead. By evenly distributing parallel computation tasks which uses data locality, the execution time for completing each stage of FFT can be reduced. Moreover, by optimizing data exchanges we minimize the communication overhead. Depending on the communication regularity, one can select appropriate parallel FFT algorithm. By using the simulation results of our cycle-accurate SystemC NoC model with a parameterizable 2-D mesh architecture, and the performance analysis in time as well as complexity, our proposed algorithms are shown to outperform other parallel FFT algorithm or high-speed DSP implementations.

Recently Network-on-Chip (NoC) technique has been proposed as a promising solution for on-chip interconnection network. However, different interface specification of integrated components raises a considerable difficulty for adopting NoC techniques. In this paper, we present a generic architecture for network interface (NI) and associated wrappers for a networked processor array (NoC based multiprocessor SoC) in order to allow systematic design flow for accelerating the design cycle. Case studies for memory and turbo decoder IPs show the feasibility and efficiency of our approach.

In this paper, we present an enhanced Network-on-Chip (NoC) architecture with efficient parallel buffer structure and its management scheme. In order to enhance the performance of the baseline router to achieve maximum throughput, a new parallel buffer architecture and its management scheme are introduced. By adopting an adjustable architecture that integrates a parallel buffer with each incoming port, the design complexity and its utilization can be optimized. By utilizing simulation-based performance evaluation and comparison with previous NoC architectures, its efficiency and superiority are proven. Major contributions of this paper are the design of the enhanced structure of a parallel buffer which is independent of routing algorithms, and its efficient management scheme for the Network-on-Chip (NoC) architecture adopting a minimal adaptive routing algorithm. As a result, the total amount of required buffers can be reduced for obtaining the maximum performance. Additionally a simple and efficient architecture of overall NoC implementation is provided by balancing the workload between parallel buffers and router logics.

We perform a fixed-point analysis for the Dolby AC-3 audio decoding algorithm, and determine the suitable multiplier wordlength (say, N) satisfying the required sound quality. Then, based on the similar simulations, we try to reduce the accumulator wordlength from the usual (8+2N) to (g+N+r) where g is the wordlength for overflow guard bits and r is the wordlength for rounding with the condition r

Low-density parity check (LDPC) codes can achieve performances close to the Shannon limit and they have been widely adopted for various communication standards. However, the irregular message exchange pattern of LDPC codes is a major challenge for decoder design. Additionally, there is a great demand for integrating diverse applications onto a single system where a flexible, scalable and efficient implementation of LDPC decoding is highly preferable. With the enormous computing power provided by integrating many processors on a single chip in advanced process technology, a multiprocessor platform is regarded as a promising solution to tackle these design challenges. In this work, we devised a parallelisation scheme to implement LDPC decoding on a multiprocessor platform. By using a distributed and cooperative way for LDPC decoding, the memory bottleneck, commonly seen in LDPC decoder design, is eliminated. Moreover, we used a graph spectra-based mapping algorithm to reduce heavy message exchanges among processors during the decoding process. Compared to the sequential mapping strategy, our approach has successfully decreased the amount of inter-processor communication by up to 48%/45%/40% for 16/32/64-processor platforms, respectively. Cycle-accurate simulation results from various LDPC codes demonstrate that desirable scalability and speedups are obtained by our approach.

The computational performance of network-on-chip (NoC) and multi-processor system-on-chip (MPSoC) for implementing cryptographic block ciphers can be improved by exploiting parallel and pipelined execution. In this paper, we present a parallel and pipeline processing method for block cipher algorithms using purely software implementation on an NoC. Algorithms are decomposed into task loops, functions and data flow for parallel and pipeline execution. Tasks are allocated by the proposed mapping strategy to each processing element (PE). In order to provide fault tolerance on nanoscale NoC circuits, we add Hamming error correction code (ECC) encoder and decoder at the network interface. The proposed parallel block cipher algorithm implementation on the fault tolerant NoC is simulated by using networked processor array (NePA), the cycle-accurate SystemC and hardware description language (HDL) model platform. Our parallel software implementation method on a multicore NoC architecture has the advantage of flexibility compared with traditional ASIC solutions. In addition, the simulation result presents that the parallel and pipeline processing approach for software block ciphers can be implemented on various NoC platforms which have different complexities and constraints.

A robust network-on-chip (NoC) architecture is presented for a 2D mesh topology that uses wormhole routing with finite first-in-first-out (FIFO) buffer-based links and a minimal adaptive routing algorithm. In designing this NoC architecture, basic network problems such as dead- lock/livelock freedom and high throughput are considered. Additionally, some issues related with actual VLSI implementation, such as design complexity and simplicity of routing algorithm, are evaluated. To verify its efficiency, a simulation-based performance evaluation and an analytical method are used. In simulation, we compare our works with other designs using standard traffic patterns used in the literature. Also a new analytical performance model is proposed. Unlike previous wormhole and adaptive routing models, the model introduced copes with variable node buffer size as well as message length under uniform random traffic pattern. The analytical model is validated by comparing with the simulation-based model using the same traffic pattern. Major contribution here is the design of two different performance models for the proposed router in NoC architecture. Specifically, a simple and accurate analytical model for NoC communication for standard applications includes the effect of variable node buffer size as well as the message length. This is the first attempt in proposing an accurate analytical model for adaptive routers.

In this paper, we present several enhanced network techniques which are appropriate for VLSI implementation and have reduced complexity, high throughput and simple routing algorithm even if basic network problems such as deadlock and livelock are considered. We develop a new packet definition to support different requirements in an MIMD message passing architecture and also verify its efficiency by comparing simulation results with various routing algorithms. Major contributions of this paper are the design of Network-on-Chip (NoC) architecture adopting a minimal adaptive routing algorithm with competitive performance and feasible design complexity, thus satisfying all the stated design goals. The proposed adaptive routing algorithm and NoC architecture offer nearly optimal performance. This can be shown by comparing with the near-optimal worst-case throughput routing algorithm for 2D-mesh networks. By providing a uniform way of constructing such network architecture, its scalability can be easily accomplished. Moreover, this network architecture can be applied to different SoC developments.