EN164  Laboratory Exercise 2: Design and Performance Analysis of a 32-bit Array Multiplier

Laboratory Exercise 2: Design and Performance Analysis of a 32-bit Array Multiplier

Brandon Diamond  Andrew Chin  Leo Meyerovich
brandon diamond@brown.edu achin@brown.edu leo meyerovich@brown.edu

March 23, 2007

1 Introduction

When designing any practical system, the computer architect faces a great number of important design choices. Of these decisions, the structure and implementation of the ALU is of particular significance; given limited resources, should all effort go toward optimizing the adder, or should some of these resources be spent implementing an in-hardware multiply? Does a blisteringly-fast adder outweigh the cost of a software multiply, or is it better to slow down the adder in order to budget for a multiply operation in hardware? As part of this lab, we have been asked to confront these design decisions, and to explore each option in depth.

To do so, we have explored three different implementations of the multiply operation using the Nios II processor and a DE2 FPGA board. The first implementation exists entirely in software and the second is synthesized in hardware; the final multiplier is implemented using custom hardware described using the Verilog hardware description language (HDL). After completing each exploration, we recorded the number of cycles required to compute a multiplication so as to allow for the comparison of each of these three design decisions.

This laboratory write-up describes the procedures utilized and the results that were observed; relevant analysis is subsequently presented. Lastly, a complete listing of code can be found at the end of this document in appendix A (page 4).

2 Procedure

2.1 Equipment

• Software:

1. Altera Nios II soft processor

2. Quartus II CAD system

3. Altera SOPC Builder and Programmer (accessed through Quartus II)

4. Verilog hardware description language

• Hardware:

1. Altera Development and Education (DE2) board

2. Cyclone II EP2C35F672C6 with EPCS16 16-Mbit serial configuration device

2.2 Setup

• Initial

1. We began by creating a new Quartus II project utilizing the Cyclone II EP2C35F672C6 FPGA aboard our DE2 development board.

2. The Nios II soft processor was instantiated via the SOPC (software-on-a-programmable-chip) utility within Quartus II for our FPGA.

3. Initially, as we expected our algorithm to run at full clock-speed, we configured the clock to run at 50 Mhz.

4. The appropriate amount of memory (30 Kbytes, 32 bit width) was specified using the On-Chip Memory Configuration wizard.

5. A USB cable was used to connect the DE2 development board to our Microsoft Windows workstation.

6. Subsequently, the JTAG UART interface was configured appropriately within Quartus II.

7. A performance counter was added to our project, and the device was configured to autoassign base addresses.

8. Finally, the complete system was generated over the course of several minutes.

• Configuring Nios II

1. The Verilog code provided was used to configure the Nios II’s pins appropriately.

2. This was achieved by importing the TA provided ‘DE2 pin assignments.csv’ file into our project.

• Programming Setup

1. Upon running the Programmer within the Quartus II environment, the USB connection was configured to utilize USB-Blaster.

2. Our project configuration file was added to the Programmer so ensure that our configuration was utilized appropriately.

3. Finally, the FPGA was configured with the above settings in place.

4. With the device configured, the Nios II EDS integrated development environment was started and configured to use our project’s .ptf file.

5. Throughout the course of development, code was written within this IDE, built for our configuration, and run as Nios II Hardware.

2.3 Approach

Initially, we set out to work through the fairly length configuration of our DE2 board and programming environment. A good deal of time was spent working to build our project appropriately and to set up the integrated development environment so as to allow us to begin writing code. We were very careful to test each step of the setup inclemently by confirming that the project was configured appropriately and, finally, by running the TA provided test code for the built-in multiply operation.

After we were certain that our project had been appropriately configured and that we understood how our system was working, we set out to implement the software multiply unit. As each member of our team is fairly familiar with the C programming language, we were able to proceed in a fairly straightforward manner. Following a brief discussion on how we intended to implement the multiply, it was a simple matter of expressing the operation in C, and executing the code on the soft processor. Fortunately, having spent so much time configuring our project earlier, we were able to get our code running fairly quickly.

Having completed the first two parts of the assignment, we set out to design our custom multiply units and adders. We proceeded carefully, first devising an algorithm, and then discovering how to express our algorithm in Verilog. While this approach did not enable us to acquire a good understanding of the Verilog syntax and semantics until several iterations into development, it did allow us to jump right in and work fairly quickly. Fortunately, we were able to implement the full adder and half adder after one or two tries; we utilized the Verilog In One Day tutorial^{1} rather thoroughly in order to do this.

After incrementally testing our one-bit adders and ensuring that these worked as expected in the simulator, we proceeded to devise our array multiplier. The approach taken here was also incremental; we began by whiteboarding until we were able to understand the array adder depicted in the lecture slides. We then worked to extrapolate a few of the details that were glazed over in lecture. Finally, we devised a set of special-cases, an inductive definition, and a collection of base cases for our array multiplier algorithm.

Subsequently, we spent some time perusing the Verilog tutorial in order to learn how to express our algorithm most efficiently. Following this research, we set out to implement each special case, followed by the rows and then columns of the multiplier using our inductive definition. Subsequently, we tied this into our code using a small wrapper module, and proceeded to test. We used the debug view thoroughly to first ensure that our special cases were correct, then each of our columns, and finally the tricky bottom row. Any impedance was resolved, and it wasn’t long until our multiplier was working appropriately. For more details on the algorithm and method used, please see below.

After testing a variety of simple multiplies by 0, 1, and so forth, we proceeded to test that our array multiplier handled overflow appropriately. By multiplying 2^{32} − 1 by powers of two, we were able to ensure that the bits were shifting to the left appropriately, and therefore, that overflow was being handled sanely. Each of our datastructures were examined by hand to confirm that our gates were arranged appropriately.

Once we were fairly confident in our circuit within the simulator, we followed the aforementioned procedure to run the code on the chip. We again tried our test cases in the C framework using the Nios II EDS IDE and obtained the same results. Finally, we ran the TA test code and confirmed that the same final value was obtained as our two prior test runs, confirming that our multiplier was fully functional.

3 Experimental Results

For each part of the lab, we compiled and ran test code (see appendix A.1 on page 4), using the three difference multiplier units. The test code simply performed some predetermined multiplications while counting the number of cycles the test code took to run. The results for each part:

In part 1 (software multiply), we found that the answer was 61556835, computed in 1923904024 cycles.

In part 2 (hardware multiply), we found that the answer was 61556835, computed in 5213 cycles. In part 3 (our custom hardware multiply), we found that the answer was 61556835, computed

in 13836 cycles.

These results line up very well with our expectations. The slowest part was clearly part 1, where the multiply operation was synthisized in software by doing a series of additions. We expected to find that this method was the slowest because of number of instructions involved in a software implementation; not only are there a bunch of addition instructions, but branching and testing is also involved. The fastest part was part 2, where we ran the test code on hardware with a built-in multiply instruction. Again, we expected this to be much faster than part 1, and were not surprised to find that it was faster than our own hardware implementation. The hardware implementation for the multiplication instruction was presumably designed by professional engineers, so it would be reasonable to assume that a good deal of time had been spent optimizing the hardware multiplier (thus being faster than our non-optimized hardware). It’s important to note how big the time difference between software multiply in hardware multiply is. In the case of these test results, the speed to compute the multiply in part 2 is nearly 370000 times faster than the software multiply.

1http://www.asic-world.com/verilog/veritut.html

Our own hardware implementation was about twice as slow as the built-in hardware multiplier, but also significantly faster than the software multiplier (by about a factor of 140000). Again, this is inline with our expectations. The important thing to note here is that even a simple hardware multiplier (such as ours) is much faster than doing a multiplication in software.

As we were unaware of exactly how the performance counter kept cycle counts, it may be that our test code ran a bit slower than if we had run it without the performance counter. However, given that we are looking at the relative speeds of the three multiplier versions, we can safely ignore any potential slowdowns due to the performance counter.

Again, it is clear that a multiply unit implemented in hardware is drastically faster than a multiply unit implemented in software.

4 Conclusion

From our experiments with the three multiply operations — and having implemented an array multiplier at the gate level — we were able to gain a great deal of insight into the various tradeoffs involved when considering a software multiply unit, a synthesized multiply unit, and a custom multiply unit for a given processor architecture. While this choice is largely application dependent, there are a number of observations that can be made with respect to our expectations as engineers as well as our analysis of each device’s performance.

Our results clearly show that a multiplier implemented in hardware is, by several orders of magnitude, faster than a software multiplication unit. Because of this, it becomes obvious why a lot of hardware has their own multiply instruction, instead of leaving it up to the software.

Certainly, despite our results, there are a number of complex factors that influence which design an architect ultimately selects over another. For example, a cheap embedded processor might be better suited to a simple, minimal architecture, leaving complex operations such as square root and multiplication to be implemented in code, whereas an expensive DSP might benefit most from lighting-fast multiplication and vector operations that are justified by the device’s target audience and application. In fact, given the performance boost we saw from using a hardware multiplier, it would seem that one must be used in a DSP in order to do real-time signal processing.

Thus, the architect would skimp on the hardware for the embedded processor, while he might pack tons and tons of functionality into the complex digital signal processor.

A Code

A.1 Test code

A.1.1 Code of part 1 and part 2

1

2 // This i s the a p p l i c a t i o n f o r part 1 and part 2 .
3 //Rename t h i s to main . cc
4 #i n c l u d e <s t d i o . h>
5 #i n c l u d e ” system . h”
6 #i n c l u d e ” a l t e r a a v a l o n p e r f o r m a n c e c o u n t e r . h”

7 8

9 #d e f i n e H LENGTH 226
10 #d e f i n e X LENGTH 226
11 #d e f i n e LENGTH 226

12 13

14 i n t h [ ] = { 6 3 8 , 4 5 1 , 4 5 , 7 8 7 , 3 6 5 , 1 3 8 , 6 5 7 , 4 9 7 , 4 5 1 , 8 4 6 , 2 6 2 , 4 7 3 , 8 5 1 , 4 2 6 ,
15 1 0 1 0 , 9 3 8 , 2 3 6 , 1 9 2 , 6 2 9 , 7 5 3 , 9 3 5 , 2 0 0 , 9 0 6 , 5 2 5 , 4 9 9 , 2 3 7 , 7 4 4 , 2 7 9 , 8 6 1 , 6 8 8 ,
16 2 3 8 , 6 6 , 4 5 3 , 3 5 1 , 6 1 9 , 3 8 8 , 9 1 4 , 9 4 6 , 1 1 2 , 8 6 9 , 3 3 1 , 7 0 8 , 2 1 9 , 7 , 1 0 0 8 , 1 0 0 8 ,

17 6 5 8 , 8 4 0 , 7 6 1 , 2 4 0 , 2 4 6 , 1 5 9 , 9 8 7 , 4 5 2 , 1 7 5 , 3 8 7 , 4 0 8 , 4 2 5 , 6 4 7 , 6 8 7 , 7 3 1 , 5 5 3 ,
18 4 3 0 , 9 0 0 , 6 3 4 , 9 9 7 , 3 7 , 6 8 8 , 8 8 2 , 7 8 4 , 1 2 5 , 9 9 8 , 8 0 1 , 2 3 0 , 6 6 6 , 9 4 7 , 3 4 2 , 5 5 3 ,
19 9 9 , 5 7 9 , 5 8 2 , 8 5 4 , 1 1 9 , 2 8 3 , 1 6 0 , 7 1 3 , 1 7 9 , 7 3 8 , 5 0 7 , 8 6 7 , 2 8 3 , 5 4 3 , 4 7 7 , 7 8 4 ,
20 9 0 3 , 1 3 8 , 5 2 0 , 6 4 1 , 8 7 , 7 1 6 , 1 0 2 1 , 5 7 6 , 7 5 0 , 4 2 5 , 5 0 4 , 5 7 8 , 8 9 3 , 7 5 5 , 7 6 0 , 6 5 9 ,
21 9 4 6 , 7 8 1 , 3 3 0 , 5 3 1 , 2 4 4 , 4 7 7 , 3 5 5 , 3 5 7 , 1 2 6 , 2 5 4 , 1 2 6 , 3 6 3 , 9 4 5 , 7 3 , 8 8 1 , 2 6 0 ,
22 5 6 1 , 8 8 5 , 2 7 8 , 1 7 9 , 5 3 8 , 2 4 3 , 7 3 7 , 4 1 7 , 1 2 5 , 4 9 1 , 4 4 0 , 6 5 8 , 9 2 5 , 2 1 7 , 2 0 5 , 1 2 5 ,
23 1 6 8 , 5 1 6 , 7 9 4 , 1 7 9 , 7 2 0 , 9 1 8 , 4 5 9 , 1 6 3 , 1 3 3 , 1 0 3 , 7 7 , 5 7 6 , 8 1 , 9 1 0 , 4 5 6 , 4 7 4 ,
24 8 7 7 , 6 3 3 , 1 6 0 , 5 1 8 , 5 3 4 , 2 5 7 , 8 8 4 , 6 6 2 , 1 7 1 , 2 9 , 4 3 6 , 1 4 8 , 5 4 2 , 4 0 , 2 3 6 , 4 , 3 7 0 ,
25 5 7 2 , 3 4 3 , 2 2 9 , 4 6 1 , 5 2 7 , 5 1 5 , 1 4 8 , 5 7 1 , 9 2 3 , 7 1 3 , 6 5 2 , 3 8 3 , 7 3 5 , 8 0 3 , 5 3 9 , 9 4 ,
26 706 ,128 ,1019 ,167 ,440 ,527 ,594 ,627 ,562 ,1019 ,224 ,270 ,464 ,302 ,475 ,
27 7 6 2 , 7 5 4 , 2 3 9 , 7 3 9 , 9 2 6 , 3 9 1 , 6 4 2 , 3 1 6 , 7 9 7 , 4 1 6 , 6 3 , 9 6 , 1 1 1 , 7 0 2 , 7 9 4 , 5 7 5 ,
28 9 7 6 , 1 0 , 1 6 , 7 5 2 };

29

30 i n t x [ ] = { 8 7 6 , 7 2 7 , 3 5 5 , 8 9 1 , 4 0 3 , 2 7 0 , 9 4 6 , 5 5 1 , 1 5 1 , 6 0 0 , 6 8 0 , 5 7 5 , 3 6 9 , 8 6 4 ,
31 6 8 0 , 7 0 5 , 3 0 , 4 2 0 , 1 0 0 6 , 6 4 7 , 8 1 7 , 6 0 3 , 9 8 2 , 7 5 2 , 8 8 4 , 1 7 2 , 6 0 5 , 9 9 1 , 2 9 3 , 6 5 8 ,
32 4 6 3 , 5 7 1 , 7 2 9 , 4 9 9 , 1 0 1 4 , 6 3 5 , 6 7 9 , 7 0 2 , 5 6 4 , 4 5 7 , 6 9 3 , 5 0 5 , 3 3 4 , 8 8 9 , 7 1 6 , 6 7 4 ,
33 6 9 9 , 3 0 2 , 5 5 1 , 1 7 5 , 1 0 2 1 , 3 8 5 , 4 4 6 , 4 9 , 9 1 0 , 1 5 8 , 6 1 1 , 3 6 6 , 7 8 7 , 2 1 7 , 2 5 2 , 6 5 6 ,
34 2 6 1 , 5 4 0 , 5 7 2 , 9 0 2 , 8 3 8 , 9 3 6 , 1 6 5 , 4 4 9 , 1 0 0 2 , 1 7 2 , 7 0 5 , 8 3 7 , 9 8 5 , 6 1 5 , 2 3 2 , 7 3 7 ,
35 5 8 5 , 4 0 4 , 3 8 9 , 1 9 9 , 2 , 5 5 5 , 8 5 8 , 9 3 2 , 7 5 9 , 4 1 5 , 2 0 0 , 9 8 5 , 4 7 0 , 6 2 9 , 7 2 6 , 2 9 8 ,
36 5 3 6 , 8 3 5 , 8 8 1 , 1 0 1 3 , 4 , 1 5 4 , 2 7 0 , 9 3 7 , 8 6 7 , 7 0 8 , 3 1 8 , 7 7 3 , 6 5 6 , 8 5 6 , 3 9 8 , 9 7 6 ,
37 1 4 4 , 8 8 3 , 9 6 1 , 4 5 3 , 2 4 0 , 4 7 9 , 2 5 7 , 6 1 0 , 5 0 0 , 9 4 3 , 1 7 3 , 6 1 5 , 1 6 1 , 5 8 7 , 3 0 , 4 7 2 ,
38 4 2 2 , 5 2 5 , 1 4 7 , 3 8 9 , 5 6 8 , 4 9 6 , 3 8 5 , 3 3 2 , 7 5 9 , 3 9 2 , 2 3 5 , 9 9 4 , 7 7 6 , 5 8 4 , 6 2 6 , 5 2 6 ,
39 7 5 8 , 1 0 0 8 , 3 1 , 4 8 6 , 8 , 9 0 7 , 6 8 3 , 7 7 3 , 7 0 2 , 4 4 , 8 2 4 , 8 0 5 , 5 7 0 , 4 9 2 , 2 5 1 , 2 2 4 , 5 0 ,
40 1 8 4 , 8 3 4 , 9 1 1 , 7 7 4 , 3 6 3 , 4 1 8 , 9 9 4 , 2 3 1 , 4 8 6 , 6 7 2 , 1 1 8 , 4 0 8 , 6 6 2 , 4 3 1 , 5 2 8 , 7 4 8 ,
41 3 1 1 , 3 8 6 , 7 9 0 , 6 4 4 , 7 9 1 , 8 5 0 , 3 8 2 , 1 9 9 , 1 6 7 , 2 8 7 , 1 2 3 , 8 1 6 , 9 4 3 , 3 2 , 2 1 , 3 4 2 ,
42 6 7 8 , 7 0 3 , 6 2 5 , 8 2 , 9 4 5 , 7 9 9 , 1 8 3 , 1 3 0 , 8 4 7 , 5 2 3 , 1 4 , 5 7 0 , 4 7 1 , 2 4 5 , 9 8 5 , 5 6 8 ,
43 2 5 6 , 2 5 6 , 3 9 , 3 1 2 , 4 9 , 7 1 8 , 4 5 9 , 8 7 5 , 7 1 , 3 1 9 , 9 0 8 , 3 5 9 , 8 8 8 , 1 0 9 , 4 9 3 , 8 0 4 ,
44 4 4 5 , 3 2 4 , 7 0 };

45 46

47 i n t t e s t F u n c t i o n 1 2 ( ) ;

48

49 i n t main parts12 ( )
50 {

51 52

53 PERF RESET(PERFORMANCE COUNTER 0 BASE) ;
54 PERF START MEASURING(PERFORMANCE COUNTER 0 BASE) ;

55 56

57 i n t r e s u l t = 0 ;
58 r e s u l t = t e s t F u n c t i o n ( ) ;

59

60 PERF STOP MEASURING(PERFORMANCE COUNTER 0 BASE) ;

61

62 a l t u 6 4 time = 0 ;
63 time = p e r f g e t s e c t i o n t i m e ( ( void ∗)PERFORMANCE COUNTER 0 BASE, 1) ;
64 p r i n t f (” That was fun , the answer i s %d , i t took %d c y c l e s \n ” , r e s u l t , time ) ;

65 66 67

68  /∗ Event loop never e x i t s . ∗/
69  while ( 1 ) ;

70

71  r e t u r n 0 ;
72 }

73 74

75 i n t t e s t F u n c t i o n ( ) {

76

77  i n t i ;
78  i n t j ;
79  i n t y = 0 ;

80

81  PERF BEGIN(PERFORMANCE COUNTER 0 BASE, 1 ) ;
82  f o r ( i =0; i < LENGTH; i ++) {

83

84  y = y + h [ i ] ∗ x [ i ] ;
85  }

86

87  PERF END(PERFORMANCE COUNTER 0 BASE, 1 ) ;

88

89  r e t u r n y ;
90 }

A.1.2 Code for part 3

1

2 // This i s the a p p l i c a t i o n that uses your m u l t i p l i e r .
3 //Make s u r e you rename t h i s to main . cc .
4 #i n c l u d e <s t d i o . h>
5 #i n c l u d e ” system . h ”
6 #i n c l u d e ” a l t e r a a v a l o n p e r f o r m a n c e c o u n t e r . h”
7 //# i n c l u d e ” conv . h”

8

9 #d e f i n e H LENGTH 226
10 #d e f i n e X LENGTH 226
11 #d e f i n e LENGTH 226

12

13 i n t h [ ] = { 6 3 8 , 4 5 1 , 4 5 , 7 8 7 , 3 6 5 , 1 3 8 , 6 5 7 , 4 9 7 , 4 5 1 , 8 4 6 , 2 6 2 , 4 7 3 , 8 5 1 , 4 2 6 ,
14 1 0 1 0 , 9 3 8 , 2 3 6 , 1 9 2 , 6 2 9 , 7 5 3 , 9 3 5 , 2 0 0 , 9 0 6 , 5 2 5 , 4 9 9 , 2 3 7 , 7 4 4 , 2 7 9 , 8 6 1 , 6 8 8 ,
15 2 3 8 , 6 6 , 4 5 3 , 3 5 1 , 6 1 9 , 3 8 8 , 9 1 4 , 9 4 6 , 1 1 2 , 8 6 9 , 3 3 1 , 7 0 8 , 2 1 9 , 7 , 1 0 0 8 , 1 0 0 8 ,
16 6 5 8 , 8 4 0 , 7 6 1 , 2 4 0 , 2 4 6 , 1 5 9 , 9 8 7 , 4 5 2 , 1 7 5 , 3 8 7 , 4 0 8 , 4 2 5 , 6 4 7 , 6 8 7 , 7 3 1 , 5 5 3 ,
17 4 3 0 , 9 0 0 , 6 3 4 , 9 9 7 , 3 7 , 6 8 8 , 8 8 2 , 7 8 4 , 1 2 5 , 9 9 8 , 8 0 1 , 2 3 0 , 6 6 6 , 9 4 7 , 3 4 2 , 5 5 3 ,
18 9 9 , 5 7 9 , 5 8 2 , 8 5 4 , 1 1 9 , 2 8 3 , 1 6 0 , 7 1 3 , 1 7 9 , 7 3 8 , 5 0 7 , 8 6 7 , 2 8 3 , 5 4 3 , 4 7 7 , 7 8 4 ,
19 9 0 3 , 1 3 8 , 5 2 0 , 6 4 1 , 8 7 , 7 1 6 , 1 0 2 1 , 5 7 6 , 7 5 0 , 4 2 5 , 5 0 4 , 5 7 8 , 8 9 3 , 7 5 5 , 7 6 0 , 6 5 9 ,
20 9 4 6 , 7 8 1 , 3 3 0 , 5 3 1 , 2 4 4 , 4 7 7 , 3 5 5 , 3 5 7 , 1 2 6 , 2 5 4 , 1 2 6 , 3 6 3 , 9 4 5 , 7 3 , 8 8 1 , 2 6 0 ,
21 5 6 1 , 8 8 5 , 2 7 8 , 1 7 9 , 5 3 8 , 2 4 3 , 7 3 7 , 4 1 7 , 1 2 5 , 4 9 1 , 4 4 0 , 6 5 8 , 9 2 5 , 2 1 7 , 2 0 5 , 1 2 5 ,
22 1 6 8 , 5 1 6 , 7 9 4 , 1 7 9 , 7 2 0 , 9 1 8 , 4 5 9 , 1 6 3 , 1 3 3 , 1 0 3 , 7 7 , 5 7 6 , 8 1 , 9 1 0 , 4 5 6 , 4 7 4 ,
23 8 7 7 , 6 3 3 , 1 6 0 , 5 1 8 , 5 3 4 , 2 5 7 , 8 8 4 , 6 6 2 , 1 7 1 , 2 9 , 4 3 6 , 1 4 8 , 5 4 2 , 4 0 , 2 3 6 , 4 , 3 7 0 ,
24 5 7 2 , 3 4 3 , 2 2 9 , 4 6 1 , 5 2 7 , 5 1 5 , 1 4 8 , 5 7 1 , 9 2 3 , 7 1 3 , 6 5 2 , 3 8 3 , 7 3 5 , 8 0 3 , 5 3 9 , 9 4 ,
25 706 ,128 ,1019 ,167 ,440 ,527 ,594 ,627 ,562 ,1019 ,224 ,270 ,464 ,302 ,475 ,
26 7 6 2 , 7 5 4 , 2 3 9 , 7 3 9 , 9 2 6 , 3 9 1 , 6 4 2 , 3 1 6 , 7 9 7 , 4 1 6 , 6 3 , 9 6 , 1 1 1 , 7 0 2 , 7 9 4 , 5 7 5 ,
27 9 7 6 , 1 0 , 1 6 , 7 5 2 };

28

29 i n t x [ ] = { 8 7 6 , 7 2 7 , 3 5 5 , 8 9 1 , 4 0 3 , 2 7 0 , 9 4 6 , 5 5 1 , 1 5 1 , 6 0 0 , 6 8 0 , 5 7 5 , 3 6 9 , 8 6 4 ,
30 6 8 0 , 7 0 5 , 3 0 , 4 2 0 , 1 0 0 6 , 6 4 7 , 8 1 7 , 6 0 3 , 9 8 2 , 7 5 2 , 8 8 4 , 1 7 2 , 6 0 5 , 9 9 1 , 2 9 3 , 6 5 8 ,
31 4 6 3 , 5 7 1 , 7 2 9 , 4 9 9 , 1 0 1 4 , 6 3 5 , 6 7 9 , 7 0 2 , 5 6 4 , 4 5 7 , 6 9 3 , 5 0 5 , 3 3 4 , 8 8 9 , 7 1 6 , 6 7 4 ,
32 6 9 9 , 3 0 2 , 5 5 1 , 1 7 5 , 1 0 2 1 , 3 8 5 , 4 4 6 , 4 9 , 9 1 0 , 1 5 8 , 6 1 1 , 3 6 6 , 7 8 7 , 2 1 7 , 2 5 2 , 6 5 6 ,
33 2 6 1 , 5 4 0 , 5 7 2 , 9 0 2 , 8 3 8 , 9 3 6 , 1 6 5 , 4 4 9 , 1 0 0 2 , 1 7 2 , 7 0 5 , 8 3 7 , 9 8 5 , 6 1 5 , 2 3 2 , 7 3 7 ,
34 5 8 5 , 4 0 4 , 3 8 9 , 1 9 9 , 2 , 5 5 5 , 8 5 8 , 9 3 2 , 7 5 9 , 4 1 5 , 2 0 0 , 9 8 5 , 4 7 0 , 6 2 9 , 7 2 6 , 2 9 8 ,
35 5 3 6 , 8 3 5 , 8 8 1 , 1 0 1 3 , 4 , 1 5 4 , 2 7 0 , 9 3 7 , 8 6 7 , 7 0 8 , 3 1 8 , 7 7 3 , 6 5 6 , 8 5 6 , 3 9 8 , 9 7 6 ,
36 1 4 4 , 8 8 3 , 9 6 1 , 4 5 3 , 2 4 0 , 4 7 9 , 2 5 7 , 6 1 0 , 5 0 0 , 9 4 3 , 1 7 3 , 6 1 5 , 1 6 1 , 5 8 7 , 3 0 , 4 7 2 ,
37 4 2 2 , 5 2 5 , 1 4 7 , 3 8 9 , 5 6 8 , 4 9 6 , 3 8 5 , 3 3 2 , 7 5 9 , 3 9 2 , 2 3 5 , 9 9 4 , 7 7 6 , 5 8 4 , 6 2 6 , 5 2 6 ,
38 7 5 8 , 1 0 0 8 , 3 1 , 4 8 6 , 8 , 9 0 7 , 6 8 3 , 7 7 3 , 7 0 2 , 4 4 , 8 2 4 , 8 0 5 , 5 7 0 , 4 9 2 , 2 5 1 , 2 2 4 , 5 0 ,
39 1 8 4 , 8 3 4 , 9 1 1 , 7 7 4 , 3 6 3 , 4 1 8 , 9 9 4 , 2 3 1 , 4 8 6 , 6 7 2 , 1 1 8 , 4 0 8 , 6 6 2 , 4 3 1 , 5 2 8 , 7 4 8 ,
40 3 1 1 , 3 8 6 , 7 9 0 , 6 4 4 , 7 9 1 , 8 5 0 , 3 8 2 , 1 9 9 , 1 6 7 , 2 8 7 , 1 2 3 , 8 1 6 , 9 4 3 , 3 2 , 2 1 , 3 4 2 ,
41 6 7 8 , 7 0 3 , 6 2 5 , 8 2 , 9 4 5 , 7 9 9 , 1 8 3 , 1 3 0 , 8 4 7 , 5 2 3 , 1 4 , 5 7 0 , 4 7 1 , 2 4 5 , 9 8 5 , 5 6 8 ,
42 2 5 6 , 2 5 6 , 3 9 , 3 1 2 , 4 9 , 7 1 8 , 4 5 9 , 8 7 5 , 7 1 , 3 1 9 , 9 0 8 , 3 5 9 , 8 8 8 , 1 0 9 , 4 9 3 , 8 0 4 ,
43 4 4 5 , 3 2 4 , 7 0 };

44

45 i n t t e s t F u n c t i o n ( ) ;

46

47 i n t main ( )
48 {

49 50

51 PERF RESET(PERFORMANCE COUNTER 0 BASE) ;
52 PERF START MEASURING(PERFORMANCE COUNTER 0 BASE) ;

53 54

55 i n t r e s u l t = 0 ;
56 r e s u l t = t e s t F u n c t i o n ( ) ;

57

58 PERF STOP MEASURING(PERFORMANCE COUNTER 0 BASE) ;

59

60 a l t u 6 4 time = 0 ;
61 time = p e r f g e t s e c t i o n t i m e ( ( void ∗)PERFORMANCE COUNTER 0 BASE, 1) ;
62 p r i n t f (” That was fun , the answer i s %d , i t took %d c y c l e s \n ” , r e s u l t , time ) ;

63 64 65

66  /∗ Event loop never e x i t s . ∗/
67  while ( 1 ) ;

68

69  r e t u r n 0 ;
70 }

71 72

73 i n t t e s t F u n c t i o n ( ) {

74

75  i n t i ;
76  i n t j ;
77  i n t y = 0 ;

78

79  PERF BEGIN(PERFORMANCE COUNTER 0 BASE, 1 ) ;
80  f o r ( i =0; i < LENGTH; i ++) {
81 y = y + ALT CI MY MULT( h [ i ] , x [ i ] ) ; //name o f the mult i n s t r u c t i o n
82  }
83  PERF END(PERFORMANCE COUNTER 0 BASE, 1 ) ;

84

85  r e t u r n y ;
86 }

A.2 Custom multiplier, in VERILOG

1 // our h a l f a d d e r .
2 // Inputs : x , y
3 // Outputs : sum , c a r r y
4 module h a l f a d d e r ( x , y , sum , c a r r y ) ;
5  input x , y ;
6  output sum , c a r r y ;

7

8  and U carry ( carry , x , y ) ;
9  xor U sum (sum , x , y ) ;

10

11 endmodule

12

13 // o u r f u l l adder
14 // i n p u t s : x , y , c a r r y i n
15 // outputs : sum , c a r r y o u t
16 module f u l l a d d e r ( x , y , c a r r y i n , sum , c a r r y o u t ) ;  //TODO f i x e d in / out order
17  input x , y , c a r r y i n ;
18  output sum , c a r r y o u t ;
19  wire and1 , and2 , and3 , sum1 ;

20

21  and U and1 ( and1 , x , y ) ,
22  U and2 ( and2 , x , c a r r y i n ) ,
23  U and3 ( and3 , y , c a r r y i n ) ;
24 or U or ( carry out , and1 , and2 , and3 ) ;
25  xor U sum (sum , x , y , c a r r y i n ) ;

26

27 endmodule

28 29

30 // our custom m u l t i p l y i n s t r u c t i o n , were we
31 // implement a carry −save array m u l t i p l i e r
32 // i n p u t s : dataa , datab ( both 32 b i t )
33 // output : myZ (64 b i t )
34 module mult (
35 dataa , // operand A <always required >

36 datab , // operand B <o p t i o n a l >
37 myZ // r e s u l t <always required >
38 ) ;

39

40 input [ 3 1 : 0 ] dataa ;
41 wire [ 3 1 : 0 ] dataa ;

42

43 input [ 3 1 : 0 ] datab ;
44 wire [ 3 1 : 0 ] datab ;

45

46 // output [ 3 1 : 0 ] r e s u l t ;
47 output [ 6 3 : 0 ] myZ;
48 wire [ 6 3 : 0 ] myZ;

49

50 // a w i r e a r r a y to connect a l l o f our h a l f − and f u l l −adders
51 wire tmps [ 3 1 : 0 ] [ 3 1 : 0 ] [ 0 : 1 ] ; // [ row ] [ column ] [ 0 = sum , 1 = c a r r y ]
52 // a s p e c i a l l y named wire array to take the r e s u l t s from the l a s t row o f adders and
connect them to the outputs
53 wire bottomrow [ 3 0 : 0 ] [ 0 : 1 ] ; // [ column ] [ 0 = sum , 1 = c a r r y ]

54

55 // some c o u n t e r s f o r our l o o p s
56 genvar r ;
57 genvar c ;

58

59 g e n e r a t e
60 // f i r s t row o f the adder
61 f o r ( c = 0 ; c < 3 2 ; c = c + 1) begin : loopa

62

63  // h a l f a d d e r ha1 ( dataa [ c ] && datab [ 0 ] , 1 ’ b0 , tmps [ 0 ] [ c ] [ 0 ] , tmps [ 0 ] [ c ] [ 1 ]
) ;
64  a s s i g n tmps [ 0 ] [ c ] [ 1 ] = 1 ’ b0 ; // a constant
65  a s s i g n tmps [ 0 ] [ c ] [ 0 ] = dataa [ c ] && datab [ 0 ] ;
66 end

67

68 // the main loop . here we connect the bulk o f our adders t o g e t h e r
69 f o r ( r = 1 ; r < 3 2 ; r = r + 1) begin : loopb
70  // c o f 31 ( l e f t column : only take in c a r r y )
71  // t h i s column o f adders needs s p e c i a l a t t e n t i o n , because i t only t a k e s in
the p r e v i o u s row ’ s c a r r y o u t
72  h a l f a d d e r ha2 ( dataa [ 3 1 ] && datab [ r ] , tmps [ r − 1 ] [ 3 1 ] [ 1 ] , tmps [ r ] [ 3 1 ] [ 0 ] , tmps [
r ] [ 3 1 ] [ 1 ] ) ;
73  // c o f 0 : 3 0
74  f o r ( c = 0 ; c < 3 1 ; c = c + 1) begin : loopc
75  // e v e r y t h i n g e l s e that ’ s not in the l e f t most column .
76  f u l l a d d e r ha3 ( dataa [ c ] && datab [ r ] , tmps [ r − 1 ] [ c ] [ 1 ] , tmps [ r −1][ c
+ 1 ] [ 0 ] ,
77  tmps [ r ] [ c ] [ 0 ] , tmps [ r ] [ c ] [ 1 ] ) ;
78  end
79 end

80

81 // r i g h t c o r n e r : c , s , no acc
82 h a l f a d d e r ha4 ( tmps [ 3 1 ] [ 0 ] [ 1 ] , tmps [ 3 1 ] [ 1 ] [ 0 ] , bottomrow [ 0 ] [ 0 ] , bottomrow [ 0 ] [ 1 ] ) ;
83 a s s i g n myZ [ 3 2 ] = bottomrow [ 0 ] [ 0 ] ; // here we a c t u a l l y connect a r e s u l t to an output

wire

84

85 f o r ( r = 0 ; r < 3 2 ; r = r + 1) begin : loope
86  // r i g h t column
87 a s s i g n myZ[ r ] = tmps [ r ] [ 0 ] [ 0 ] ; // connect the r e s u l t to the output w i r e s
88 end

89

90 f o r ( c = 1 ; c < 3 1 ; c = c + 1) begin : l o o p f
91  // bottom row
92  f u l l a d d e r ha5 ( tmps [ 3 1 ] [ c ] [ 1 ] , tmps [ 3 1 ] [ c + 1 ] [ 0 ] , bottomrow [ c − 1 ] [ 1 ] ,
bottomrow [ c ] [ 0 ] , bottomrow [ c ] [ 1 ] ) ;
93 a s s i g n myZ[ c + 3 2 ] = bottomrow [ c ] [ 0 ] ; // connect the r e s u l t to the output

w i r e s

94 end

95

96 // f i n a l l y , connect the l a s t o f the outputs from our array o f adders to the output

w i r e s

97 a s s i g n myZ [ 6 3 ] = bottomrow [ 3 0 ] [ 1 ] ;

98

99 endgenerate

100 101

102 endmodule

103 104 105

106 module my mult (
107 dataa , // operand A <always required >
108 datab , // operand B <o p t i o n a l >
109 r e s u l t // r e s u l t <always required >
110 ) ;

111 112

113 input [ 3 1 : 0 ] dataa ;
114 input [ 3 1 : 0 ] datab ;
115 output [ 3 1 : 0 ] r e s u l t ;
116 wire [ 6 3 : 0 ] myZ;

117

118 mult t e s t m u l t ( dataa , datab , myZ) ;

119

120 a s s i g n r e s u l t = myZ [ 3 1 : 0 ] ; // only connect the lower 32 b i t s

121 122 123 124

125 endmodule

126 127

128 // neat t e s t c a s e .
129 module t e s t ( ) ;

130

131 reg [ 3 1 : 0 ] dataa ;
132 reg [ 3 1 : 0 ] datab ;
133 wire [ 3 1 : 0 ] r e s u l t ;

134

135 wire r e s s ;
136 wire r e s c ;

137

138 i n i t i a l begin
139  // somem debugging s t u f f to help use monitor the output o f our custom adder
140  $monitor (”num1:%d num2:%d r e s u l t :%d ” , dataa , datab , r e s u l t ) ;
141  dataa = 4294967295;
142  datab = 4 ;

143 144

145 end

146

147 // f u l l a d d e r argh ( 1 ’ b1 , 1 ’ b1 , 1 ’ b1 , r e s s , r e s c ) ;
148 my mult argh ( dataa , datab , r e s u l t ) ;

149

150 i n i t i a l begin
151  // $monitor (” r e s s : %d\ n r e s c : %d ” , r e s s , r e s c ) ;

152

153  $monitor (” r e s num1:%d num2:%d r e s u l t :%d ” , dataa , datab , r e s u l t ) ;
154 end

155

156 endmodule