Date: Tuesday 26 March 2019
Time: 11:30 - 13:00
Location / Room: Room 6
Chair:
Martin Trefzer, University of York, UK
Co-Chair:
Lukas Sekanina, Brno University of Technology, CZ
Achieving computational and resource-efficiency is often promised by emerging technologies. This session addresses various aspects of efficiency in the context of quantum and approximate computing. Simulation of quantum computations is very computationally expensive. The first paper shows how a smart utilization of decision diagrams can significantly accelerate this process. Approximate computing is often advocated as an approach enabling to build more resource-efficient computing systems. The second paper of this session deals with an automated circuit approximation method capable of exploiting data distributions observable in the target application. The third paper presents a new application for approximate circuits in the area of wireless sensor networks. Finally, an efficient approximate random dropout technique for training acceleration of neural networks running on GPU is proposed in the fourth paper.
| Time | Label | Presentation Title Authors |
|---|---|---|
| 11:30 | 2.6.1 | MATRIX-VECTOR VS. MATRIX-MATRIX MULTIPLICATION: POTENTIAL IN DD-BASED SIMULATION OF QUANTUM COMPUTATIONS Speaker: Alwin Zulehner, Johannes Kepler University Linz, AT Authors: Alwin Zulehner and Robert Wille, Johannes Kepler University Linz, AT Abstract The simulation of quantum computations basically boils down to the multiplication of vectors (describing the respective quantum state) and matrices (describing the respective quantum operations). However, since those matrices/vectors are exponential in size, most of the existing solutions (relying on arrays for their representation) are either limited to rather small quantum systems or require substantial hardware resources. To overcome these shortcomings, solutions based on decision diagrams (DD-based simulation) have been proposed recently. They exploit redundancies in quantum states as well as matrices and, by this, allow for a compact representation and manipulation. This offers further (unexpected) potential. In fact, simulation has been conducted thus far by applying one operation (i.e. one matrix-vector multiplication) after another. Besides that, there is the possibility to combine several operations (requiring a matrix-matrix multiplication) before applying them to a vector. But since, from a theoretical perspective, matrix-vector multiplication is significantly cheaper than matrix-matrix multiplication, the potential of this direction was rather limited thus far. In this work, we show that this changes when decision diagrams are employed. In fact, their more compact representation frequently makes matrix-matrix multiplication more beneficial—leading to substantial improvements by exploiting the combination of operations. Experimental results confirm the proposed strategies for combining operations lead to speed-ups of several factors or—when additionally exploiting further knowledge about the considered instance—even of several orders of magnitudes. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 12:00 | 2.6.2 | AUTOMATED CIRCUIT APPROXIMATION METHOD DRIVEN BY DATA DISTRIBUTION Speaker: Lukas Sekanina, Brno University of Technology, CZ Authors: Zdenek Vasicek, Vojtech Mrazek and Lukas Sekanina, Brno University of Technology, CZ Abstract We propose an application-tailored data-driven fully automated method for functional approximation of combinational circuits. We demonstrate how an application-level error metric such as the classification accuracy can be translated to a component-level error metric needed for an efficient and fast search in the space of approximate low-level components that are used in the application. This is possible by employing a weighted mean error distance (WMED) metric for steering the circuit approximation process which is conducted by means of genetic programming. WMED introduces a set of weights (calculated from the data distribution measured on a selected signal in a given application) determining the importance of each input vector for the approximation process. The method is evaluated using synthetic benchmarks and application-specific approximate MAC (multiply-and-accumulate) units that are designed to provide the best trade-offs between the classification accuracy and power consumption of two image classifiers based on neural networks. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 12:30 | 2.6.3 | TRADING DIGITAL ACCURACY FOR POWER IN AN RSSI COMPUTATION OF A SENSOR NETWORK TRANSCEIVER Speaker: Paul Detterer, Eindhoven University of Technology, NL Authors: Paul Detterer, Cumhur Erdin, Majid Nabi, Jose Pineda de Gyvez, Twan Basten and Hailong Jiao, Eindhoven University of Technology, NL Abstract Emerging Wireless Sensor Network (WSN) applications require more energy efficiency in the wireless transceivers, though the conventional energy efficient design techniques are reaching their limits. To handle the rigid power and energy constraints in the Digital BaseBand (DBB) of WSNs, we introduce approximate computing in DBB processing as a new power reduction method. The Received Signal Strength Indicator (RSSI) computation is a key element in DBB processing. We evaluate the trade-off in RSSI computation between Quality-of-Service (QoS) and power consumption through circuit-level approximation. RSSI elements are approximated in such a way that error propagation is minimized. In an industrial 40-nm CMOS technology, substantial power savings are achieved with limited accuracy loss, both at circuit level and at network level in a low-power listening WSN scenario. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 12:45 | 2.6.4 | APPROXIMATE RANDOM DROPOUT FOR DNN TRAINING ACCELERATION IN GPGPU Speaker: Li Jiang, Shanghai Jiao Tong University, CN Authors: Zhuoran Song, Ru Wang, Dongyu Ru, Zhenghao Peng, Hongru Huang, Hai Zhao, Xiaoyao Liang and Li Jiang, Shanghai Jiao Tong University, CN Abstract The training phases of Deep neural network (DNN) consumes enormous processing time and energy. Compression techniques utilizing the sparsity of DNNs can effectively accelerate the inference phase of DNNs. However, it can be hardly used in the training phase because the training phase involves dense matrix-multiplication using General Purpose Computation on Graphics Processors (GPGPU), which endorse regular and structural data layout. In this paper, we propose the Approximate Random Dropout that replaces the conventional random dropout of neurons and synapses with a regular and online generated patterns to eliminate the unnecessary computation and data access. We develop a SGD-based Search Algorithm that producing the distribution of dropout patterns to compensate the potential accuracy loss. We prove our approach is statistically equivalent to the previous dropout method. Experiments results on multilayer perceptron (MLP) and long short-term memory (LSTM) using well-known benchmarks show that the speedup rate brought by the proposed Approximate Random Dropout ranges from 1.18-2.16 (1.24-1.85) when dropout rate is 0.3-0.7 on MLP (LSTM) with negligible accuracy drop. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 13:00 | IP1-8, 229 | ACCURACY AND COMPACTNESS IN DECISION DIAGRAMS FOR QUANTUM COMPUTATION Speaker: Alwin Zulehner, Johannes Kepler University Linz, AT Authors: Alwin Zulehner1, Philipp Niemann2, Rolf Drechsler3 and Robert Wille1 1Johannes Kepler University Linz, AT; 2Cyber-Physical Systems, DFKI GmbH, DE; 3University of Bremen, DE Abstract Quantum computation is a promising research field since it allows to conduct certain tasks exponentially faster than on conventional machines. As in the conventional domain, decision diagrams are heavily used in different design tasks for quantum computation like synthesis, verification, or simulation. However, unlike decision diagrams for the conventional domain, decision diagrams for quantum computation as of now suffer from a trade-off between accuracy and compactness that requires parameter fine-tuning on a case-by-case basis. In this work, we—for the first time—describe and evaluate the effects of this trade-off. Moreover, we propose an alternative approach that utilizes an algebraic representation of the occurring irrational numbers and outline how this can be incorporated in a decision diagram in order to overcome this trade-off. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 13:01 | IP1-9, 458 | ONE METHOD - ALL ERROR-METRICS: A THREE-STAGE APPROACH FOR ERROR-METRIC EVALUATION IN APPROXIMATE Speaker: Saman Fröhlich, University of Bremen/DFKI GmbH, DE Authors: Saman Fröhlich1, Daniel Grosse2 and Rolf Drechsler2 1University of Bremen/DFKI, DE; 2University of Bremen, DE Abstract Approximate Computing is a design paradigm that makes use of the error tolerance inherited by many applications, such as machine learning, media processing and data mining. The goal of Approximate Computing is to trade off accuracy for performance in terms of computation time, energy consumption and/or hardware complexity. In the field of circuit design for Approximate Computing, error-metrics are used to express the degree of approximation. Evaluating these error-metrics is a key challenge. Several approaches exist, however, to this day not all relevant metrics can be evaluated with formal methods. Recently, Symbolic Computer Algebra (SCA) has been used to evaluate error-metrics during approximate hardware generation. In this paper, we generalize the idea to use SCA and propose a methodology which is suitable for formal evaluation of all established error-metrics. This approach can be divided into three-stages: (i) Determine the remainder of the AC circuit wrt.the specification using SCA, (ii) build an Algebraic Decision Diagram (ADD) to represent the remainder and (iii) evaluate each error-metric by a tailored ADD traversal algorithm. Besides being the first to propose a closed formal method for evaluation of all relevant error-metrics, we are the first to ever propose formal algorithms for the evaluation of the worst-case-relative and the average-case-relative error-metrics. In the experiments, we apply our algorithms to a large and well-known benchmark set. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 13:02 | IP1-10, 657 | REVERSIBLE PEBBLING GAME FOR QUANTUM MEMORY MANAGEMENT Speaker: Giulia Meuli, EPFL, CH Authors: Giulia Meuli1, Mathias Soeken1, Martin Roetteler2, Nikolaj Bjorner2 and Giovanni De Micheli3 1EPFL, CH; 2Microsoft, US; 3École Polytechnique Fédérale de Lausanne (EPFL), CH Abstract Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. In this work, we propose an automatic tool for quantum memory management. We show how this problem exactly matches the reversible pebbling game. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed tool empowers the designer with the flexibility required to explore the trade-off between memory resources and number of operations. We present two show-cases to prove the validity of our approach. First, we apply the algorithm to straight-line programs, widely used in cryptographic applications. Second, we perform a comparison with the existing approach, showing an average improvement of 52.77%. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 13:00 | End of session Lunch Break in Lunch Area
On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area. Lunch Breaks (Lunch Area)On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the Lunch Area to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area. Tuesday, March 26, 2019
Wednesday, March 27, 2019
Thursday, March 28, 2019
|