2.6 Computational and resource-efficiency in quantum and approximate computing

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 Zulehner¹, Philipp Niemann², Rolf Drechsler³ and Robert Wille¹ ¹Johannes Kepler University Linz, AT; ²Cyber-Physical Systems, DFKI GmbH, DE; ³University 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öhlich¹, Daniel Grosse² and Rolf Drechsler² ¹University of Bremen/DFKI, DE; ²University 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 Meuli¹, Mathias Soeken¹, Martin Roetteler², Nikolaj Bjorner² and Giovanni De Micheli³ ¹EPFL, CH; ²Microsoft, US; ³É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 Coffee Breaks in the Exhibition 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 Coffee Break 10:30 - 11:30 Lunch Break 13:00 - 14:30 Keynote Lecture "Leonardo da Vinci, Humanism and Engineering between Florence and Milan" by Claudio Giorgione in room 1 13:50 - 14:20 Coffee Break 16:00 - 17:00 Wednesday, March 27, 2019 Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:30 Keynote Lecture "Heterogeneous, High Scale Computing in the Era of Intelligent, Cloud-Connected" by David Pellerin, Amazon, US in room 1 13:50 - 14:20 Coffee Break 16:00 - 17:00 Thursday, March 28, 2019 Coffee Break 10:00 - 11:00 University Booth Best Demo Award Presentation at the University Booth 10:30 Lunch Break 12:30 - 14:00 Keynote Lecture "A Fundamental Look at Models and Intelligence" by Edward A. Lee, University of California, Berkeley, US in room 1 13:20 - 13:50 Coffee Break 15:30 - 16:00

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 Zulehner¹, Philipp Niemann², Rolf Drechsler³ and Robert Wille¹
¹Johannes Kepler University Linz, AT; ²Cyber-Physical Systems, DFKI GmbH, DE; ³University 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öhlich¹, Daniel Grosse² and Rolf Drechsler²
¹University of Bremen/DFKI, DE; ²University 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 Meuli¹, Mathias Soeken¹, Martin Roetteler², Nikolaj Bjorner² and Giovanni De Micheli³
¹EPFL, CH; ²Microsoft, US; ³É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

Coffee Breaks in the Exhibition 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

Coffee Break 10:30 - 11:30
Lunch Break 13:00 - 14:30
Keynote Lecture "Leonardo da Vinci, Humanism and Engineering between Florence and Milan" by Claudio Giorgione in room 1 13:50 - 14:20
Coffee Break 16:00 - 17:00

Wednesday, March 27, 2019

Coffee Break 10:00 - 11:00
Lunch Break 12:30 - 14:30
Keynote Lecture "Heterogeneous, High Scale Computing in the Era of Intelligent, Cloud-Connected" by David Pellerin, Amazon, US in room 1 13:50 - 14:20
Coffee Break 16:00 - 17:00

Thursday, March 28, 2019

Coffee Break 10:00 - 11:00
University Booth Best Demo Award Presentation at the University Booth 10:30
Lunch Break 12:30 - 14:00
Keynote Lecture "A Fundamental Look at Models and Intelligence" by Edward A. Lee, University of California, Berkeley, US in room 1 13:20 - 13:50
Coffee Break 15:30 - 16:00