CODEWITHSUNDEEP
performancetimeverilogcpu-architecture
Prashant Vaidyanathan
Prashant Vaidyanathan

Reputation: 488

Comparing Time by and Time complexity of Algorithms for Computer Arithmetic

I am currently working on a project where I am trying to find which Algorithm is better when implemented in a Chip-Level design. I am pushing these to my FPGA board. I am writing the code in Verilog. What I need is a rubric to compare

a) Time Complexity of the 2 functions.

b) Worst Case timings

c) Power Consumption

For eg,

Method 1: prod = mult1 * mult2;

Where mult1 and mult2 are two 8 bit inputs.

Method 2: prod = ((mult1+mult2-100) * 100) + ((100-mult1) * (100-mult2))

Where mult1 and mult2 are two 8 bit inputs.

So I am interested in knowing the total time it takes for the chip to compute the product, from the time the 2 inputs are passed in, and the product is calculated.

The Algorithms I am dealing with are both O(n). So I know it doesn't matter asymptotically. However, I am interested in knowing the exact worse case timings taken when implemented on an FPGA or ASIC board so that I can try to improve the functions. I also understand that these calculations take nanoseconds to compute, however, that is what I am trying to improve.

I saw a couple of journal publications which claimed to have a faster algorithm. However, when I implemented the same using Xilinx and using the Synthesis Reports, I was getting different results.

Is there a software that calculates the power consumption, and worst case timings? Or could anyone point me to some article that could help me out here?

Upvotes: 1

Views: 245

Answers (1)

Tim
Tim

Reputation: 35933

Regarding the time complexity and worst case timing, these will be dependent on exactly how you write the algorithm, and the target fpga you are using.

To understand the length of time it takes to execute a computation, this depends on the clock frequency of the FPGA, and the number of clock cycles it takes to perform your algorithm. If your multiplication algorithm is single cycle, then the time it takes to compute will be simply the clock period of the fpga. Large multiplication circuits are typically not single cycle however, due to their complexity. Exactly what you get depends on your input code, the synthesizer, and the kind of fpga you are using.

Typically your FPGA synthesis tools can tell you what is the worst case timing of your design in the post-synthesis report. If you want to improve the worst case timing, then you can add pipeline stages to the multiplication to break up the work and increase clock frequency.

Measuring power consumption will also be heavily dependent on the fpga you use and the synthesized netlist that you are loading. Altera and Xilinx offer power estimators for their fpgas (probably other vendors as well), but I'm not sure if there are any vendor-agnostic power estimators out there.

Long story short, to get the metrics you want you'll need to work with the synthesis tools of the FPGA you are planning to use.

Upvotes: 3

Related Questions