Published papers

Three-dimensional stack memory which provides both high-bandwidth access and large capacity is a promising technology for next-generation computer systems. While a large number of memory cubes increase the aggregate memory capacity, the communication latency and power consumption increase significantly owing to its low-radix large-diameter packet network. In this context, we propose a memory-cube network called Diagonal Memory Network (DMN). A diagonal network topology, its floor layout, and its lightweight router were designed for low-latency and low-voltage memory-read communication. DMN routing efficiently avoids deadlocks of packets, although it allows each packet transmitted to a processor to use both bypassing and original datapaths. Our evaluation results show that the DMN router decreases the use of hardware resources by more than 31% compared with a conventional virtual channel router. The DMN router reduces energy consumption by 13% and 67% to transit a packet along with the original datapath and bypassing datapath, respectively. Furthermore, using flit-level discrete event simulation, a DMN topology achieves high throughput and latency that is lower than that of existing network topologies using conventional packet routers.

A fast and reliable LiDAR (Light Detection and Ranging) SLAM (Simultaneous Localization and Mapping) system is the growing need for autonomous mobile robots, which are used for a variety of tasks such as indoor cleaning, navigation, and transportation. To bridge the gap between the limited processing power on such robots and the high computational requirement of the SLAM system, in this paper we propose a unified accelerator design for 2D SLAM algorithms on resource-limited FPGA devices. As scan matching is the heart of these algorithms, the proposed FPGA-based accelerator utilizes scan matching cores on the programmable logic part and users can switch the SLAM algorithms to adapt to performance requirements and environments without modifying and re-synthesizing the logic part. We integrate the accelerator into two representative SLAM algorithms, namely particle filter-based and graph-based SLAM. They are evaluated in terms of resource utilization, processing speed, and quality of output results with various real-world datasets, highlighting their algorithmic characteristics. Experiment results on a Pynq-Z2 board demonstrate that scan matching is accelerated by 13.67-14.84x, improving the overall performance of particle filter-based and graph-based SLAM by 4.03-4.67x and 3.09-4.00x respectively, while maintaining the accuracy comparable to their software counterparts and even state-of-the-art methods.

Since deep learning workloads perform a large number of matrix operations on training data, GPUs (Graphics Processing Units) are efficient especially for the training phase. A cluster of computers each of which equips multiple GPUs can significantly accelerate the deep learning workloads. More specifically, a back-propagation algorithm following a gradient descent approach is used for the training. Although the gradient computation is still a major bottleneck of the training, gradient aggregation and optimization impose both communication and computation overheads, which should also be reduced for further shortening the training time. To address this issue, in this paper, multiple GPUs are interconnected with a PCI Express (PCIe) over 10Gbit Ethernet (10GbE) technology. Since these remote GPUs are interconnected with network switches, gradient aggregation and optimizers (e.g., SGD, AdaGrad, Adam, and SMORMS3) are offloaded to FPGA-based 10GbE switches between remote GPUs; thus, the gradient aggregation and parameter optimization are completed in the network. The proposed FPGA-based 10GbE switches with the four optimizers are implemented on NetFPGA-SUME board. Their resource utilizations are increased by PEs for the optimizers, and they consume up to 56% of the resources. Evaluation results using four remote GPUs connected via the proposed FPGA-based switch demonstrate that these optimizers are accelerated by up to 3.0x and 1.25x compared to CPU and GPU implementations, respectively. Also, the gradient aggregation throughput by the FPGA-based switch achieves up to 98.3% of the 10GbE line rate.

Currently there has been increasing demand for real-time training on resource-limited IoT devices such as smart sensors, which realizes standalone online adaptation for streaming data without data transfers to remote servers. OS-ELM (Online Sequential Extreme Learning Machine) has been one of promising neural-network-based online algorithms for on-chip learning because it can perform online training at low computational cost and is easy to implement as a digital circuit. Existing OS-ELM digital circuits employ fixed-point data format and the bit-widths are often manually tuned, however, this may cause overflow or underflow which can lead to unexpected behavior of the circuit. For on-chip learning systems, an overflow/underflow-free design has a great impact since online training is continuously performed and the intervals of intermediate variables will dynamically change as time goes by. In this paper, we propose an overflow/underflow-free bit-width optimization method for fixed-point digital circuits of OS-ELM. Experimental results show that our method realizes overflow/underflow-free OS-ELM digital circuits with 1.0x - 1.5x more area cost compared to the baseline simulation method where overflow or underflow can happen.

The design of the network topology of a large-scale parallel computer system can be represented as an order/degree problem in the graph theory. To solve the order/degree problem, we have to obtain all-pairs-shortest-path (APSP) for the graph. A conventional APSP algorithm for GPUs is based on the adjacency matrix (ADJ-APSP). When focusing on low-degree and unweighted graphs, most of the matrix elements are zero in the first few iterations of the algorithm. We will further speed up the APSP algorithm by treating the adjacency matrix as a sparse matrix in the first iterations of the algorithm. Evaluation results show that our proposed algorithm on a single GPU (NVIDIA GeForce RTX 3080) reduces the execution time by up to 32.7 % compared to the conventional algorithm.

Network throughput has become an important issue for big-data analysis on Warehouse-Scale Computing (WSC) systems. It has been reported that randomly-connected inter-switch networks can enlarge the network throughput. For irregular networks, a multi-path routing method called k-shortest path routing is conventionally utilized. However, it cannot efficiently exploit longer-than-shortest paths that would be detour paths to avoid bottlenecks. In this work, a novel routing method called koptimized path routing to achieve high throughput is proposed for irregular networks. We introduce a heuristic to select detour paths that can avoid bottlenecks in the network to improve the average-case network throughput. Experimental results by network simulation show that the proposed k-optimized path routing can improve the saturation throughput by up to 18.2% compared to the conventional k-shortest path routing. Moreover, it can reduce the computation time required for optimization to 1/2760 at a minimum compared to our previously proposed method.

This paper aims at establishing a method for designing high-performance network topologies to bridge a gap between theoretical and practical studies. To this end, we present a novel graph called a host-switch graph, which consists of host vertices and switch vertices with maximum degree 1 and r, respectively. This graph represents a network topology of a practical parallel/distributed computer system with host computers connected by r-port switches. We discuss important metrics for designing high-performance interconnection networks: the host-to-host average shortest path length (h-ASPL) and the bisection width (BiW). In particular, we explore a method for constructing host-switch graphs with low h-ASPL and high BiW that connect the fixed number of hosts via any number of r-port switches. We demonstrate that the number of switches that provides the minimum h-ASPL can mathematically be approximated, and the minimum number of switches that provides a certain BiW can experimentally be approximated. On the basis of the approximations, we propose a randomized algorithm for searching host-switch graphs. We then apply the graphs to interconnection networks and compare them with typical network topologies. As compared with the torus, the dragonfly, and the fat-tree, our networks attain higher performance and smaller power and costs.

Message queuing systems that deliver messages from publishers to subscribers play an important role to collect data from IoT devices. Traditional message queuing systems have improved their performance in the context of transferring log data from publishers such as Web servers to subscribers that analyze the log data. In this case, both publishers and subscribers have been assumed to have enough buffer capacity and can transfer data as jumbo frame packets for high efficiency. In recent IoT applications, however, publishers are small sensors or edge devices with low-power processors and limited memory capacity. Vast numbers of such publishers produce relatively small packets. Such a lot of small messages significantly decrease the efficiency of conventional message queuing systems. To address this issue, a dedicated message queuing logic can be implemented on FPGA-based network interface card (FPGA NIC). However, a serious issue of such in-NIC approach is a limited memory capacity on the FPGA NIC. To handle message overflow of the in-NIC cache, in this paper, it is combined with a large in-kernel software cache. More specifically, we propose a multilevel message queuing cache combining in-NIC and in-kernel memories, called MultiMQC. The multilevel cache improves the read performance. Regarding the write performance, MultiMQC introduces a batch transfer that packs small incoming messages into a single batch. We implemented MultiMQC using NetFPGA-SUME board as in-NIC cache and Linux Netfilter framework as in-kernel cache. The experimental results demonstrate that the write throughput is increased in proportion to the batch size. When pull requests hit in the in-NIC cache, the read throughput reaches 95.8% of 10GbE line rate in four 10GbE interfaces.

Various parallel applications, such as numerical convergent computation and multimedia processing, have intrinsic tolerance to inaccuracies that allow soft errors, i.e. bit flips, on a chip. However, existing Network-on-Chips (NoCs) guarantee error-free data transfer; thus, encountering limits to reduce the power consumption. In this context, we propose an approximate dual-voltage NoC, called AxNoC. An AxNoC router uses a per-flit look-ahead power management so that headers and important-data flits are perfectly transferred at a high voltage while the remaining flits may incur bit flips by decreasing the supply voltage. An AxNoC router isolates the critical path when the supply voltage is low since such a critical path is enabled only at high voltage. The critical path isolation enables low-voltage operation to work at the same operating frequency at high voltage. An AxNoC router was implemented using a 28nm process and the evaluation results illustrate its efficiency to reduce the power consumption reaching up to 43% while incurring a small area overhead that does not exceed 6.2%. We also demonstrate that AxNoC exhibits an acceptable accuracy illustrated in a sufficiently small geomean of error.

Recently proposed irregular networks can reduce the latency for both on-chip and off-chip systems with a large number of computing nodes and thus can improve the performance of parallel application. However, these networks usually suffer from deadlocks in routing packets when using a naive minimal path routing algorithm. To solve this problem, we focus attention on a lately proposed theory that generalizes the turn model to maintain the network performance with deadlock-freedom. The theorems remain a challenge of applying themselves to arbitrary topologies including fully irregular networks. In this paper, we advance the theorems to completely general ones. To apply the idea of the turn model to arbitrary topologies, we introduce a concept of regions that define continuous directions of channels on an n-dimensional space. Moreover, we provide a feasible implementation of a deadlock-free routing method based on our advanced theorem. To reduce the latency and the number of required Virtual Channels (VCs) with this method, a heuristic approach is introduced to reduce the number of prohibited turns between channels. Experimental results show that the routing method based on our proposed theorem can improve the network throughput by up to 138 % compared to a conventional deterministic minimal routing method. Moreover, it can reduce the latency by up to 2.9 % compared to another fully adaptive routing method.

Wireless interconnects based on inductive coupling technology are compelling propositions for designing 3-D integrated chips. This work addresses the heat dissipation problem on such systems. Although effective cooling technologies have been proposed for systems designed based on Through Silicon Via (TSV), their application to systems that use inductive coupling is problematic because of increased wireless-communication distance. For this reason, we propose two methods for designing sparse 3-D chips layouts and Networks on Chip (NoCs) based on inductive coupling. The first method computes an optimized 3-D chip layout and then generates a randomized network topology for this layout. The second method uses a standard stack chip layout with a standard network topology as a starting point, and then deterministically transforms it into either a "staircase" or a "checkerboard" layout. We quantitatively compare the designs produced by these two methods in terms of network and application performance. Our main finding is that the first method produces designs that ultimately lead to higher parallel application performance, as demonstrated for nine OpenMP applications in the NAS Parallel Benchmarks.

Semi-supervised anomaly detection is an approach to identify anomalies by learning the distribution of normal data. Backpropagation neural networks (i.e., BP-NNs) based approaches have recently drawn attention because of their good generalization capability. In a typical situation, BP-NN-based models are iteratively optimized in server machines with input data gathered from the edge devices. However, (1) the iterative optimization often requires significant efforts to follow changes in the distribution of normal data (i.e., concept drift), and (2) data transfers between edge and server impose additional latency and energy consumption. To address these issues, we propose ONLAD and its IP core, named ONLAD Core. ONLAD is highly optimized to perform fast sequential learning to follow concept drift in less than one millisecond. ONLAD Core realizes on-device learning for edge devices at low power consumption, which realizes standalone execution where data transfers between edge and server are not required. Experiments show that ONLAD has favorable anomaly detection capability in an environment that simulates concept drift. Evaluations of ONLAD Core confirm that the training latency is 1.95x∼6.58x faster than the other software implementations. Also, the runtime power consumption of ONLAD Core implemented on PYNQ-Z1 board, a small FPGA/CPU SoC platform, is 5.0x∼25.4x lower than them.

Cloud computing has established a convenient approach for computing offloading, where the data produced by edge devices is gathered and processed in a centralized server. However, it results in critical issues related to latency. Recently, a neural network-based on-device learning approach is proposed, which offers a solution to the latency problem by relocating processing data to edge devices; even so, a single edge device may face insufficient training data to train a high-quality model, because of its limited available processing capabilities and energy resources. To address this issue, we extend the work to a federated learning system which enables the edge devices to exchange their trained parameters and update local models. However, in federated learning for anomaly detection, the reliability of local models would be different. For example, a number of trained models are likely to contain the features of anomalous data because of noise corruption or anomaly detection failure. Besides, as the communication protocol amongst edges could be exploited by attackers, the training data or model weights may have potential risks of being poisoned. Therefore, when we design a federated training algorithm, we should carefully select the local models that participate in model aggregation. In this work, we leverage an observed dataset to compute prediction errors, so that the unsatisfying local models can be excluded from federated training. Experimental results show that the federated learning approach improves anomaly detection accuracy. Besides, the proposed model aggregation solution achieves obvious improvement compared with the popular Federated Averaging method.

Blockchain is a distributed ledger system based on P2P network and originally used for a crypto currency system. The P2P network of Blockchain is maintained by full nodes which are in charge of verifying all the transactions in the network. However, most Blockchain user nodes do not act as full nodes, because workload of full nodes is quite high for personal mobile devices. Blockchain search queries, such as confirming balance, transaction contents, and transaction histories, from many users go to the full nodes. As a result, search throughput of full nodes would be a new bottleneck of Blockchain system, because the number of full nodes is less than the number of users of Blockchain systems. In this paper, we propose an acceleration method of Blockchain search using GPUs. More specifically, we introduce an array-based Patricia tree structure suitable for GPU processing so that we can make effective use of Blockchain feature that there are no update and delete queries. In the evaluations, the proposed method is compared with an existing GPU-based key-value search and a conventional CPU-based search in terms of the throughput of Blockchain key search. As a result, the throughput of our proposal is 3.4 times higher than that of the existing GPU-based search and 14.1 times higher than that of the CPU search when the number of keys is 80 ×220 and the key length is 256-bit in Blockchain search queries.

Blockchain is core technology for cryptocurrency and it is possible to become fundamental platform for industry and business. Especially, a blockchain-based digital asset transfer system using Internet of Things (IoT) products has recently been considered as a new practical platform, but the protocol limits performance. Previous research has improved performance by proposing new protocols, but further improvement is necessary for dealing with increasing transactions via IoT products. Therefore, we propose an in-Network Interface Card (in-NIC) processing approach using a Field Programmable Gate Array (FPGA) to improve performance of a blockchain-based transfer system. To be more concrete, we design and implement a prototype NIC with a key-value data store written in a P4 language on the FPGA that has four 10Gigabit Ethernet (10GbE) network interfaces. The prototype system supports frequently-used commands (CREATE, ISSUE, TRANSFER and REFER) for transferring digital asset. It reduces time for processing a kernel network protocol stack and accessing the data store. In fact, we measured throughput and latency of our prototype system compared to those of a blockchain software application. As a result, we found that our solution is able to obtain throughput 6.04 times higher on average and latency 15.4 times lower on average for all typical blockchain operations.

A back-propagation algorithm following a gradient descent approach is used for training deep neural networks. Since it iteratively performs a large number of matrix operations to compute the gradients, GPUs (Graphics Processing Units) are efficient especially for the training phase. Thus, a cluster of computers each of which equips multiple GPUs can significantly accelerate the training phase. Although the gradient computation is still a major bottleneck of the training, gradient aggregation and parameter optimization impose both communication and computation overheads, which should also be reduced for further shortening the training time. To address this issue, in this paper, multiple GPUs are interconnected with a PCI Express (PCIe) over 10 Gbit Ethernet (10GbE) technology. Since these remote GPUs are interconnected via network switches, gradient aggregation and optimizers (e.g., SGD, Adagrad, Adam, and SMORMS3) are offloaded to an FPGA-based network switch between a host machine and remote GPUs; thus, the gradient aggregation and optimization are completed in the network. Evaluation results using four remote GPUs connected via the FPGA-based 10GbE switch that implements the four optimizers demonstrate that these optimization algorithms are accelerated by up to 3. 0x and 1. 25x compared to CPU and GPU implementations, respectively. Also, the gradient aggregation throughput by the FPGA-based switch achieves 98.3% of the 10GbE line rate.

ODENet is a deep neural network architecture in which a stacking structure of ResNet is implemented with an ordinary differential equation (ODE) solver. It can reduce the number of parameters and strike a balance between accuracy and performance by selecting a proper solver. It is also possible to improve the accuracy while keeping the same number of parameters on resource-limited edge devices. In this paper, using Euler method as an ODE solver, a part of ODENet is implemented as a dedicated logic on a low-cost FPGA (Field-Programmable Gate Array) board, such as PYNQ-Z2 board. As ODENet variants, reduced ODENets (rODENets) each of which heavily uses a part of ODENet layers and reduces/eliminates some layers differently are proposed and analyzed for low-cost FPGA implementation. They are evaluated in terms of parameter size, accuracy, execution time, and resource utilization on the FPGA. The results show that an overall execution time of an rODENet variant is improved by up to 2.66 times compared to a pure software execution while keeping a comparable accuracy to the original ODENet.

In statistical analysis and data mining, change-point detection that identifies the change-points which are times when the probability distribution of time series changes has been used for various purposes, such as anomaly detections on network traffic and transaction data. However, computation cost of a conventional AR (Auto-Regression) model based approach is too high and infeasible for online. In this paper, an AR model based online change-point detection algorithm, called ChangeFinder, is implemented on an FPGA (Field Programmable Gate Array) based NIC (Network Interface Card). The proposed system computes the change-point score from time series data received from 10 GbE (10 Gbit Ethernet). More specifically, it computes the change-point score at the 10 GbE NIC in advance of host applications. This paper aims to reduce the host workload and improve change-point detection performance by offloading ChangeFinder algorithm from host to the NIC. As evaluations, change-point detection in the FPGA NIC is compared with a baseline software implementation and those enhanced by two network optimization techniques using DPDK and Netfilter in terms of throughput. The result demonstrates 16.8x improvement in change-point detection throughput compared to the baseline software implementation. The throughput achieves 83.4% of the 10 GbE line rate.

Blockchain is a distributed ledger system composed of a P2P network and is used for a wide range of applications, such as international remittance, inter-individual transactions, and asset conservation. In Blockchain systems, tamper resistance is enhanced by the property of transaction that cannot be changed or deleted by everyone including the creator of the transaction. However, this property also becomes a problem that unintended transaction created by miss operation or secret key theft cannot be corrected later. Due to this problem, once an illegal transaction such as theft occurs, the damage will expand. To suppress the damage, we need countermeasures, such as detecting illegal transaction at high speed and correcting the transaction before approval. However, abnormality detection in the Blockchain at high speed is computationally heavy, because we need to repeat the detection process using various feature quantities and the feature extractions become overhead. In this paper, to accelerate abnormality detection, we propose to cache transaction information necessary for extracting feature in GPU device memory and perform both feature extraction and abnormality detection in the GPU. We employ abnormality detection using K-means algorithm based on the conditional features. When the number of users is one million and the number of transactions is 100 millions, our proposed method achieves 37.1 times faster than CPU processing method and 16.1 times faster than GPU processing method that does not perform feature extraction on the GPU.

Over the past decade, the power consumption has been one of the main design challenges in Network-on-Chips (NoCs) as it significantly defines the performance of a given Chip-Multiprocessor (CMP). Body bias control is one of the solutions that provide an efficient trade-off between leakage power and performance. However, employing such a method is not straightforward since several factors should be taken into consideration, especially when adaptively implemented on-chip. In this paper, we propose a new router design and on-chip body bias control mechanism to adaptively control the body bias voltages supply in ultra low-power NoC systems. With the help of a light-weight monitoring circuit, the proposed router predicts the traffic load at each input-port and accordingly adjusts its pipeline depth in a fine-grained fashion. To satisfy the timing constraints, the router adaptively supplies each one of its input-ports with the appropriate body bias voltages to either boost the performance or to reduce the leakage power at the standby state. The evaluation results, using the SOTB 65nm Fully Depleted Silicon On Insulator (FD-SOI) technology, shows the ability of the proposed router in reducing both dynamic and static energies. When compared to two fixed-pipeline baseline routers (3-stages and 2-stages), the total energy reduction could reach up to 67% and 59%, respectively. At the same time, a reasonable performance tendency can be obtained with less than 6% area overhead.