EDAthon 2020

Problem 1: Bitwidth-Quantized Training of Neural Networks

A trend in AI deployment is to move the computation from cloud (central) to the user end (edge) where the data are generated. This is sometimes known as edge computing which is usually done on hardware-constrained terminal devices or IoT boards with limited storage and processing power. Consequently, it is important for the AI neural networks (NN) to be of small size while preserving certain output accuracy. A way to achieve lightweight NNs is to quantize the weights and biases to a small bitwidth (e.g., a reduction from FP32 to INT8 already represents a 4X reduction in storage). Specifically, in this problem, we will investigate the quantized training of LeNet on MNIST with different bitwidths, namely, to explore the hardware-efficient low-bitwidth quantized training of a simple neural network for handwritten digit image classification. In particular, the complexity-accuracy trade-off will be systematically investigated.

NOTE: This problem requires high-performance GPU hardware.

Reference:

[1] Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations, https://arxiv.org/abs/1609.07061

[2] TensorQuant - A Simulation Toolbox for Deep Neural Network Quantization, https://arxiv.org/abs/1710.05758

Problem 2: Loop Scheduling for Switching-Activity Minimization on VLIW processor

VLIW (Very Long Instruction Word) architecture has been widely utilized in DSP processors. A VLIW processor has multiple functional units (FUs) and can process several instructions simultaneously. As it has an instruction bus with large capacitance, transition activities on the instruction bus consume a significant fraction of total power dissipation in a processor. In this question, your task is to reduce the bus switching activities by implementing an instruction-level scheduling algorithm considering dependencies among instructions.

Reference:

[1] Zili Shao, Bin Xiao, Chun Xue, Qingfeng Zhuge, and Edwin H-M. Sha. "Loop scheduling with timing and switching-activity minimization for VLIW DSP." ACM Transactions on Design Automation of Electronic Systems (TODAES) 11.1 (2006): 165-185.

[2] Zili Shao, Qingfeng Zhuge, Meilin Liu, Bin Xiao and Edwin H-M. Sha. "Switching-Activity Minimization on Instruction-level Loop Scheduling for VLIW DSP Applications." IEEE Computer Society Press Proceedings, 2004.

Problem 3: 3D Pattern Routing

In global routing, we need to plan the route of each net. This question is on the technique called 3D pattern routing, by which we combine pattern routing and layer assignment, and it is possible to produce optimal solutions with respect to the patterns under consideration in terms of a cost function in wire length and routability. Please refer to the following paper for reference.

Reference:

[1] “CUGR: Detailed-Routability-Driven 3D Global Routing with Probabilistic Resource Model”, Jinwei Liu, Chak-Wa Pui, Fangzhou Wang, and Evangeline FY Young, DAC 2020.

Problem 4: Floorplanning with optimum area utilization under constraints

In floorplanning stage of physical implementation of VLSI, we arrange the position of each modules/blocks and assign port locations. We’d like to minimize the global bounding box of a floorplan along with other objectives such as total wirelength, signal delays. In the problem, you will be given a series of rectangles and you would try to place all of them closely on a canvas without overlapping. We expect a good solution that minimize the area of the global bounding box. Some hard/soft constrains will be applied in this problem, eg certain area has blockage that rectangles cannot be placed, some rectanges should be placed near each other, etc.

Reference:

[1] B*-Tree：Chang Y C, Chang Y W, Wu G M, et al. B*-trees: A new representation for non-slicing floorplans[C]//Proceedings of the 37th Annual Design Automation Conference. 2000: 458-463.

[2] BSG(Bounded slicing grid)- structure：Nakatake S, Fujiyoshi K, Murata H, et al. Module placement on BSG-structure and IC layout applications[C]//Proceedings of International Conference on Computer Aided Design. IEEE, 1996: 484-491.

[3] Simulated Annealing：https://en.wikipedia.org/wiki/Simulated_annealing

[4] linear programming：Chen P, Kuh E S. Floorplan sizing by linear programming approximation[C]//Proceedings of the 37th Annual Design Automation Conference. 2000: 468-471.

Problem 5: Systolic array for GEMM and SPMV

With the success of TPU on accelerating CNN (convolutional neural network) which is invented by Google, application specific accelerator is receiving particular high attention. For TPU, the core is a systolic array, which is a well-known architecture for accelerating GEMM (General Matrix Matrix multiplication) operation. In this problem, we will have two parts.

For the first part, you need to use HDL to implement a 6*6 systolic array to perform GEMM. In the reference [1], you can find the paper on implementing a 3*3 systolic array on FPGA.

For the second part, you need to use HDL to implement a systolic array to perform spmv (sparse matrix vector multiplication). In the reference [2], you can find how to design such hardware circuit on FPGA.

NOTE: This problem requires you to have an IDE to debug HDL.

Reference:

[1] Vucha, Mahendra, and Arvind Rajawat. "Design and FPGA implementation of systolic array architecture for matrix multiplication." International Journal of Computer Applications 26.3 (2011): 18-22.

[2] E. Montagne and R. Surós, "Systolic Sparse Matrix Vector Multiply in the Age of TPUs and Accelerators," 2019 Spring Simulation Conference (SpringSim), Tucson, AZ, USA, 2019, pp. 1-10.