• Graphics Processing Units (GPUs) support dynamic voltage and frequency scaling (DVFS) in order to balance computational performance and energy consumption. However, there still lacks simple and accurate performance estimation of a given GPU kernel under different frequency settings on real hardware, which is important to decide best frequency configuration for energy saving. This paper reveals a fine-grained model to estimate the execution time of GPU kernels with both core and memory frequency scaling. Over a 2.5x range of both core and memory frequencies among 12 GPU kernels, our model achieves accurate results (within 3.5\%) on real hardware. Compared with the cycle-level simulators, our model only needs some simple micro-benchmark to extract a set of hardware parameters and performance counters of the kernels to produce this high accuracy.
  • With huge amounts of training data, deep learning has made great breakthroughs in many artificial intelligence (AI) applications. However, such large-scale data sets present computational challenges, requiring training to be distributed on a cluster equipped with accelerators like GPUs. With the fast increase of GPU computing power, the data communications among GPUs have become a potential bottleneck on the overall training performance. In this paper, we first propose a general directed acyclic graph (DAG) model to describe the distributed synchronous stochastic gradient descent (S-SGD) algorithm, which has been widely used in distributed deep learning frameworks. To understand the practical impact of data communications on training performance, we conduct extensive empirical studies on four state-of-the-art distributed deep learning frameworks (i.e., Caffe-MPI, CNTK, MXNet and TensorFlow) over multi-GPU and multi-node environments with different data communication techniques, including PCIe, NVLink, 10GbE, and InfiniBand. Through both analytical and experimental studies, we identify the potential bottlenecks and overheads that could be further optimized. At last, we make the data set of our experimental traces publicly available, which could be used to support simulation-based studies.
  • Rectifier neuron units (ReLUs) have been widely used in deep convolutional networks. An ReLU converts negative values to zeros, and does not change positive values, which leads to a high sparsity of neurons. In this work, we first examine the sparsity of the outputs of ReLUs in some popular deep convolutional architectures. And then we use the sparsity property of ReLUs to accelerate the calculation of convolution by skipping calculations of zero-valued neurons. The proposed sparse convolution algorithm achieves some speedup improvements on CPUs compared to the traditional matrix-matrix multiplication algorithm for convolution when the sparsity is not less than 0.9.
  • Many recent deep learning platforms rely on third-party libraries (such as cuBLAS) to utilize the computing power of modern hardware accelerators (such as GPUs). However, we observe that they may achieve suboptimal performance because the library functions are not used appropriately. In this paper, we target at optimizing the operations of multiplying a matrix with the transpose of another matrix (referred to as NT operation hereafter), which contribute about half of the training time of fully connected deep neural networks. Rather than directly calling the library function, we propose a supervised learning based algorithm selection approach named MTNN, which uses a gradient boosted decision tree to select one from two alternative NT implementations intelligently: (1) calling the cuBLAS library function; (2) calling our proposed algorithm TNN that uses an efficient out-of-place matrix transpose. We evaluate the performance of MTNN on two modern GPUs: NVIDIA GTX 1080 and NVIDIA Titan X Pascal. MTNN can achieve 96\% of prediction accuracy with very low computational overhead, which results in an average of 54\% performance improvement on a range of NT operations. To further evaluate the impact of MTNN on the training process of deep neural networks, we have integrated MTNN into a popular deep learning platform Caffe. Our experimental results show that the revised Caffe can outperform the original one by an average of 28\%. Both MTNN and the revised Caffe are open-source.
  • Deep learning has been shown as a successful machine learning method for a variety of tasks, and its popularity results in numerous open-source deep learning software tools. Training a deep network is usually a very time-consuming process. To address the computational challenge in deep learning, many tools exploit hardware features such as multi-core CPUs and many-core GPUs to shorten the training time. However, different tools exhibit different features and running performance when training different types of deep networks on different hardware platforms, which makes it difficult for end users to select an appropriate pair of software and hardware. In this paper, we aim to make a comparative study of the state-of-the-art GPU-accelerated deep learning software tools, including Caffe, CNTK, MXNet, TensorFlow, and Torch. We first benchmark the running performance of these tools with three popular types of neural networks on two CPU platforms and three GPU platforms. We then benchmark some distributed versions on multiple GPUs. Our contribution is two-fold. First, for end users of deep learning tools, our benchmarking results can serve as a guide to selecting appropriate hardware platforms and software tools. Second, for software developers of deep learning tools, our in-depth analysis points out possible future directions to further optimize the running performance.
  • Energy efficiency has become one of the top design criteria for current computing systems. The dynamic voltage and frequency scaling (DVFS) has been widely adopted by laptop computers, servers, and mobile devices to conserve energy, while the GPU DVFS is still at a certain early age. This paper aims at exploring the impact of GPU DVFS on the application performance and power consumption, and furthermore, on energy conservation. We survey the state-of-the-art GPU DVFS characterizations, and then summarize recent research works on GPU power and performance models. We also conduct real GPU DVFS experiments on NVIDIA Fermi and Maxwell GPUs. According to our experimental results, GPU DVFS has significant potential for energy saving. The effect of scaling core voltage/frequency and memory voltage/frequency depends on not only the GPU architectures, but also the characteristic of GPU applications.
  • Memory access efficiency is a key factor in fully utilizing the computational power of graphics processing units (GPUs). However, many details of the GPU memory hierarchy are not released by GPU vendors. In this paper, we propose a novel fine-grained microbenchmarking approach and apply it to three generations of NVIDIA GPUs, namely Fermi, Kepler and Maxwell, to expose the previously unknown characteristics of their memory hierarchies. Specifically, we investigate the structures of different GPU cache systems, such as the data cache, the texture cache and the translation look-aside buffer (TLB). We also investigate the throughput and access latency of GPU global memory and shared memory. Our microbenchmark results offer a better understanding of the mysterious GPU memory hierarchy, which will facilitate the software optimization and modelling of GPU architectures. To the best of our knowledge, this is the first study to reveal the cache properties of Kepler and Maxwell GPUs, and the superiority of Maxwell in shared memory performance under bank conflict.
  • Technology of autonomous vehicles (AVs) is getting mature and many AVs will appear on the roads in the near future. AVs become connected with the support of various vehicular communication technologies and they possess high degree of control to respond to instantaneous situations cooperatively with high efficiency and flexibility. In this paper, we propose a new public transportation system based on AVs. It manages a fleet of AVs to accommodate transportation requests, offering point-to-point services with ride sharing. We focus on the two major problems of the system: scheduling and admission control. The former is to configure the most economical schedules and routes for the AVs to satisfy the admissible requests while the latter is to determine the set of admissible requests among all requests to produce maximum profit. The scheduling problem is formulated as a mixed-integer linear program and the admission control problem is cast as a bilevel optimization, which embeds the scheduling problem as the major constraint. By utilizing the analytical properties of the problem, we develop an effective genetic-algorithm-based method to tackle the admission control problem. We validate the performance of the algorithm with real-world transportation service data.
  • In cognitive radio networks, rendezvous is a fundamental operation by which two cognitive users establish a communication link on a commonly-available channel for communications. Some existing rendezvous algorithms can guarantee that rendezvous can be completed within finite time and they generate channel-hopping (CH) sequences based on the whole channel set. However, some channels may not be available (e.g., they are being used by the licensed users) and these existing algorithms would randomly replace the unavailable channels in the CH sequence. This random replacement is not effective, especially when the number of unavailable channels is large. In this paper, we design a new rendezvous algorithm that attempts rendezvous on the available channels only for faster rendezvous. This new algorithm, called Interleaved Sequences based on Available Channel set (ISAC), constructs an odd sub-sequence and an even sub-sequence and interleaves these two sub-sequences to compose a CH sequence. We prove that ISAC provides guaranteed rendezvous (i.e., rendezvous can be achieved within finite time). We derive the upper bound on the maximum time-to-rendezvous (MTTR) to be O(m) (m is not greater than Q) under the symmetric model and O(mn) (n is not greater than Q) under the asymmetric model, where m and n are the number of available channels of two users and Q is the total number of channels (i.e., all potentially available channels). We conduct extensive computer simulation to demonstrate that ISAC gives significantly smaller MTTR than the existing algorithms.
  • Most of existing rendezvous algorithms generate channel-hopping sequences based on the whole channel set. They are inefficient when the set of available channels is a small subset of the whole channel set. We propose a new algorithm called ZOS which uses three types of elementary sequences (namely, Zero-type, One-type, and S-type) to generate channel-hopping sequences based on the set of available channels. ZOS provides guaranteed rendezvous without any additional requirements. The maximum time-to-rendezvous of ZOS is upper-bounded by O(m1*m2*log2M) where M is the number of all channels and m1 and m2 are the numbers of available channels of two users.
  • To enhance environmental sustainability, many countries will electrify their transportation systems in their future smart city plans. So the number of electric vehicles (EVs) running in a city will grow significantly. There are many ways to re-charge EVs' batteries and charging stations will be considered as the main source of energy. The locations of charging stations are critical; they should not only be pervasive enough such that an EV anywhere can easily access a charging station within its driving range, but also widely spread so that EVs can cruise around the whole city upon being re-charged. Based on these new perspectives, we formulate the Electric Vehicle Charging Station Placement Problem (EVCSPP) in this paper. We prove that the problem is non-deterministic polynomial-time hard. We also propose four solution methods to tackle EVCSPP and evaluate their performance on various artificial and practical cases. As verified by the simulation results, the methods have their own characteristics and they are suitable for different situations depending on the requirements for solution quality, algorithmic efficiency, problem size, nature of the algorithm, and existence of system prerequisite.