Graph convolutional networks (GCNs) are emerging neural network models designed to process graph-structured data. Due to massively parallel computations using irregular data structures by GCNs, traditional processors such as CPUs, GPUs, and TPUs exhibit significant inefficiency when performing GCN inferences. Even though researchers have proposed several GCN accelerators, the prior dataflow architectures struggle with inefficient data utilization due to the divergent and irregularly structured graph data. In order to overcome such performance hurdles, we propose a hybrid dataflow architecture for sparse-dense matrix multiplications (SpDeMMs), called HyMM. HyMM employs disparate dataflow architectures using different data formats to achieve more efficient data reuse across varying degree levels within graph structures, hence HyMM can reduce off-chip memory accesses significantly. We implement the cycle-accurate simulator to evaluate the performance of HyMM. Our evaluation results demonstrate HyMM can achieve up to 4.78× performance uplift by reducing off-chip memory accesses by 91% compared to the conventional non-hybrid dataflow.

Dynamic voltage scaling (DVS) is one of the most effective techniques for reducing energy consumption on battery-operated embedded systems. According to the granularity of units to which voltage scaling is applied, the DVS problem can be divided into two subproblems: (i) inter-task DVS problem and (ii) intra-task DVS problem. A lot of effective DVS techniques have addressed either one of the two subproblems, but none of them have attempted to solve both simultaneously. This paper examines the problem of combined inter- and intra-task DVS, called the combined DVS (CDVS) problem. We solve the CDVS problem in two embedded system domains: one is systems with a sleep state and the other without sleep state. For systems without sleep state, we propose a close-to-optimal algorithm for the CDVS problem. We show that the algorithm is optimal when the power is a quadratically increasing function of the system's clock speed or the applied voltage level. For systems with a sleep state, we propose a refinement algorithm that fine-tunes the solution to the CDVS problem without sleep state to further reduce energy consumption by exploiting sleep state. Experimental results show that our proposed CDVS algorithm without sleep state is able to reduce the energy consumption by 12.5% on average over the results by the method that sequentially performs two existing inter- and intra-task DVS techniques, which are both optimal under no sleep state. Furthermore, our CDVS algorithm with a sleep state can reduce the energy consumption by 7.1% on average over the results by the conventional representative method that utilizes sleep state, but does not consider intra- and inter-task DVS simultaneously.

This paper presents a set of comprehensive techniques for the intratask voltage-scheduling problem to reduce energy consumption in hard real-time tasks of embedded systems. Based on the execution profile of the task, a voltage-scheduling technique that optimally determines the operating voltages to individual basic blocks in the task is proposed. The obtained voltage schedule guarantees minimum average energy consumption. The proposed technique is then extended to solve practical issues regarding transition overheads, which are totally or partially ignored in the existing approaches. Finally, a technique involving a novel extension of our optimal scheduler is proposed to solve the scheduling problem in a discretely variable voltage environment. We also present a novel voltage set-up technique to determine each voltage level for customizable systems-on-chips (SoCs) with discretely variable voltages. In summary, it is confirmed from experiments that the proposed optimal scheduling technique reduces energy consumption by 20.2% over that of one of the state-of-the-art schedulers (Shin and Kim, 2001) and, further, the extended technique in a discrete-voltage environment reduces energy consumption by 45.3% on average.

Dynamic voltage scaling (DVS) which is an effective energy minimization technique has been well-studied in recent years. Yet the problem of selecting voltage levels for multiple voltage DVS systems remains an unresolved issue. In this paper, we present a novel technique for dealing with the problem of finding k operating voltages to minimize the energy consumption (voltage set-up problem). A new formulation of the voltage set-up problem is given to make our solution less dependent on the specific DVS scheme. Then it is solved optimally using dynamic programming in polynomial time. With almost the same time complexity we extend the proposed technique to explore the design space to determine the best number of voltage levels. It is confirmed from the experiments that the proposed voltage set-up solution reduces energy consumption by 19.2% on average over that of previous technique [7].

It is generally accepted that the dynamic voltage scaling (DVS) is one of the most effective techniques for energy minimization. According to the granularity of units to which voltage scaling is applied, the DVS problem can be divided into two subproblems: (i) inter-task DVS problem; and (ii) intra-task DVS problem. A lot of effective DVS techniques have addressed either one of the two subproblems, but none of them have attempted to solve both simultaneously, which is mainly due to an excessive computation complexity to solve it optimally. This work addresses this core issue, that is, Can the combined problem be solved effectively and efficiently? More specifically, our work shows, for a set of inter-dependent tasks, that the combined DVS problem can be solved optimally in polynomial time. Experimental results indicate that the proposed integrated DVS technique is able to reduce energy consumption by 10.6% on average over the results by (Zhang et al., 2002 and Seo et al., 2004) (i.e., a straightforward combination of two optimal inter- and intra task DVS techniques).

This paper presents a set of comprehensive techniques for the intratask voltage scheduling problem to reduce energy consumption in hard real-time tasks of embedded systems. Based on the execution profile of the task, a voltage scheduling technique that optimally determines the operating voltages to individual basic blocks in the task is proposed. The obtained voltage schedule guarantees minimum average energy consumption. The proposed technique is then extended to solve practical issues regarding transition overheads, which are totally or partially ignored in the existing approaches. Finally, a technique involving a novel extension of our optimal scheduler is proposed to solve the scheduling problem in a discretely variable voltage environment. In summary, it is confirmed from experiments that the proposed optimal scheduling technique reduces energy consumption by 20.2 % over that of one of the state-of-the-art schedulers [11] and, further, the extended technique in a discrete voltage environment reduces energy consumption by 45.3 % on average.

With the increasing design complexity and performance requirement, data arrays in behavioral specification are usually mapped to memories in behavioral synthesis. This paper describes a new algorithm that overcomes two limitations of the previous works on the problem of memory-allocation and array-mapping to memories. Specifically, its key features are a tight link to the scheduling effect, which was totally or partially ignored by the existing memory synthesis systems, and supporting nonuniform access speeds among the ports of memories, which greatly diversify the possible (practical) memory configurations. Experimental data on a set of benchmark filter designs are provided to show the effectiveness of the proposed exploration strategy in finding globally best memory configurations.

With the increasing design complexity and performance requirement, data arrays in behavioral specification are usually mapped to fast on-chip memories in behavioral synthesis. This paper describes a new algorithm that overcomes two limitations of the previous works on the problem of memory-allocation and array-mapping to memories. Specifically, its key features are (1) a tight link to the scheduling effect, which was totally or partially ignored by the existing memory synthesis systems, and supporting (2) non-uniform access speeds among the ports of memories, which greatly diversify the possible (practical) memory configurations. Experimental data on a set of benchmark filter designs are provided to show the effectiveness of the proposed exploration strategy in finding globally best memory configurations.

This paper presents a new dynamic load balancing algorithm for hypercube multicomputers with faulty nodes. The emphasis in our method is on obtaining global load information and performing task migration using "short paths" in a synchronous manner so that a minimal amount of communication overhead is required. To accomplish this, we present an algorithm for constructing a new logical topology from a hypercube topology with faulty nodes. This new topology is used to obtain the global load information and to perform task migration. Simulation results are used to evaluate the performance of our dynamic load balancing method. The proposed strategy shows good performance in the case of a small number of faulty nodes when compared with previous methods.