The Verilog programming contest is now closed!

Are you the kind who always wanted to design digital circuits, but found the breadboard approach frustrating and time consuming? Ever wondered how ICs were designed starting from their specification but without going as far down as the transistor level? In short, we are talking of Computer Aided Design or the exciting area of Hardware description languages, where programming languages take on a whole different meaning: they describe functional pieces of hardware and not a sequence of executable instructions.

The contest will be a freestyle one where you will be given the description of a circuit that needs to be designed along with a set of test cases that need to be verified in order to ascertain that the circuit actually works. You are free to choose the hardware description language of your choice to develop the circuit. So, if you wanted to do things like implementing packet look ups in hardware, signal processing in hardware, or a PID controller, this is the contest for you. This is your chance to explore and learn what it takes to make an IC, to the extent that at the end of it you would probably be left wondering how Jack Kilby ever designed the first IC completely by hand !! 

Problems 0 to 5 all carry weightage in increasing order of difficulty.

This is more like Verilog Warm Up.

1. Design and implement a Floating Point adder for IEEE 32 bit standard floating point numbers. This one's a sitter, so we ll give you 3 points for a correct answer and an additional 3 points for efficiency given by 3/(1 + t/50) where t is the number of clock cycles. As mentioned above, if you can pipeline it, we ll double your score.
2. Design and implement a Floating Point multiplier for 32 bit IEEE floating point numbers. Same scoring pattern as above.

Problem 1:

You have 2n characters on a square grid. The characters consist of n different alphabets such that each alphabet occurs exactly 2 times. The characters are placed at the coordinates (1,0), (2,0), ..., (2n, 0).

Your task is to draw a path for each pair of same alphabet. Each path should be composed of vertical or horizontal line segments between grid points. No two paths can intersect or touch each other. No path may cross the y=0 line. Each path can only touch the y=0 line at the position of the two characters it is connecting, so the first and last line segment of each path must be vertical.

Given an arrangement of characters, give the minimum height of a solution, or indicate if no solution exists. The height is defined as the difference between the highest and lowest Y-coordinates of the paths used.

Example :

Input
a a b c b c

Solution

The minimum height is 2 in this case.

You will be given a grid as input and you need to output whether a solution exists and if so, what is it?

5 points for correctness, and a further 5 points for efficiency given by the following formula: E=5/(1+t), t is the number of simulation clock cycles taken to produce the output in the worst case. The code must be written using only structural modelling except for the stimulus block or an initial block that reads the grid of characters at the beginning of the simulation. In other words it should be a parallel hardware implementation and not a software solution.

 

Two arbitrarily long numbers (both numbers have the same number of digits) come in as a stream of digits, one after the other MSB first, LSB after an arbitrarily long time. You have to add them and display them on the screen as soon as possible. Your processor has finite storage space so you cant buffer them or something. Design and implement a solution in Verilog that takes as inputs two streams and does the above task. You can assume that every digit of each of the streams gets latched in to a register on every clock cycle. We are looking to optimize two metrics:

1. The worst case delay in printing the output once all digits of both the streams (upto the LSB) have been seen.
2. The amount of storage space used

5 points for correctness, and a further 5 points for efficiency given by the following formula: E=5/(1+(t+s)/5), t is the number of simulation clock cycles taken to produce the output in the worst case, s is the storage space used in bytes. The code must be written using only structural or behavioural modelling.

 

Design a system to implement Lempel-Ziv Compression Algorithm. Here you are supposed to generate a dictionary on the fly and output the compressed text. The decoder should only take the compressed text and output the decompressed text without any explicit dictionary supplied to it.

You have to read the input from a file which will be a sequence of characters and write the output to another file. Design two modules, one each for compression and decompression.

10 points for correctness, and a further 10 points for efficiency given by the following formula: E=10/(1+1/r), r is the compression ratio (ie the ratio of output file size to input file size for the compression engine). The code must be written using only structural or behavioural modelling.

 

Design a system to implement the Hough Transform, a commonly used image processing algorithm (Wiki this) that is used to detect straight lines in an image. The Hough Transform works by converting an image into another alternative representation where each straight line shows up as a peak in the parameter domain of straight lines ie the (m,c) space or the (rho,theta) space of the image. You will be given a 2-D image matrix as input, and an intensity threshold, and you must produce another 2-D matrix in the new parameter space as output. The peaks ie the (m,c) locations in the new image correspond to the parameters of the straight lines in the original image. The program will be judged on the correctness first and then the efficiency. 15 points for correctness, and a further 15 points for efficiency given by the following formula:

E=15/(1+t), t is the number of simulation clock cycles taken to produce the output in the worst case.

The code must be written using only structural modelling except for the stimulus block or an initial block that reads the matrix of the image at the beginning of the simulation. In other words it should be a parallel hardware implementation and not a software solution.

 

Consider a system that does the following:

You are given a Verilog description of a circuit in the form of a gate level netlist written in a given representation say A. You need to design a 'system' S that takes this representation of the gate level net list called A above, understands what circuit it represents, and generates a test bench to verify this circuit's functionality. The generated test bench code must be Verilog code that can be subsequently compiled and either synthesised or executed on the Verilog Discrete Event Simulator. The challenge is to write this system S itself in Verilog so that, in effect you are creating some sort of a meta tester IC that takes as input the gate level description of the circuit for which the test bench is to be generated. It outputs another gate level net list that can serve as a test bench for the original circuit. The program will be judged on the correctness first, and then the efficiency. 20 points for correctness, and a further 20 points for efficiency given by the following formula: E=20/(1+t), t is the number of simulation clock cycles taken to produce the output in the worst case.

The code must be written using only structural modelling except for the stimulus block or an initial block that reads the netlist representation at the beginning of the simulation. In other words it should be a parallel hardware implementation and not a software solution.

The gate level netlist of the circuit will be given in the form of standard Verilog structural code ie:

module «xyz»

wire ...;
wire ...;
and(a,b,c,d);
or(e,d,e,r);
.
.
.

endmodule

The output produced by the system S or the meta tester IC or the Verilog code for the system C, all of which are merely different representations of the same abstraction must be a test system that exhaustively tests the given circuit and which does so in the shortest time. The bound on the maximum number of variables in the boolean gate level net list is 8. And the time t mentioned above is the worst case number of clock cycles over the different instances of representation A that we use as sample inputs.

So, the system S must first read the input, then parse it and determine the circuit in its own internal form, and subsequently generate a test bench Verilog circuit that tests the original circuit given as input, in an exhaustive manner. You are basically writing a hardware compiler.

Rules :

1. Contest is open to students only.
2. Maximum of 3 members in a team are allowed. One person can't be part of more than one team.
3. Languages allowed: Verilog.
4. There will be problems with graded levels of difficulty where each problem is worth a different number of points.
5. Every submission will be tested against a set of benchmarks that shall be known to the participants along with the problems. Code need not be synthesizable.
6. Multiple submissions for the contest will be allowed until the date of closing of the event.
7. Compilation will be done on iverilog (version 0.9.1). We advise you to write compiler version independent code.
8. Any sort of malacious activity will lead to immediate disqualification of the team in question.
9. Coords have the authority to suspend/disqualify any team at any stage of the contest, if they suspect any malpractices/plagiarism.

 

Submission Guidelines:

1. Final date for submission: March 7, 2010.
   Submit your entries through the online portal only.
2. In all cases, only a hardware implementation is desired. Essentially the idea is to exploit the fact that with Verilog code you have access to as much hardware as you need, and infinite parallelism upto the extent permitted by data dependencies. If you can come up with a pipelined version of any of these circuits, we ll double your score.
3. We reserve the right to check your code and disallow it in case we find that the solution you have implemented has been implemented in software or if we find wrong clock periods (see below).
4. Besides, we shall also use it to check that the space used (if mentioned in the problem statement) is constant across different problem instances.
5. You may use read and write system calls in Verilog to read from files on the hard disk.
6. Use a gate delay of 1 simulation clock cycle for any gate level code. Any assignment statements can be assumed to be instantaneous.
7. Please do not ASSUME. Check back with us in case of any doubt.
8. Code need not be synthesisable.

FAQ :

1. I am newbie to hardware design. Where and how can I practice for it?
A>Cadence holds quite a few electronic design contests. Google obviously.
If you need a book:Verilog HDL by Samir Palnitkar.
2. How long would this contest be held?
A>The contest will open around the middle of January and would go on till the end of March. Keep watching this space for updates.
3. What all languages can I use to code?

A>Verilog

Prize Money:

1st Place:	Rs. 6000
2nd Place:	Rs. 4000
3rd Place:	Rs. 2000

Anirudh S.K.
Arpit Joshi
Email: verilog[at]exebit.org