The Scholars' Avenue

Very Large Scale Innovation

conf1Circuit boards have certainly come a long way over the decades. Were one have approached Messrs. Shockley, Brattain and Bardeen back in 1947 and suggested to them that their little invention would soon be packed, over 60 million a chip, one would surely have been excluded from the gene pool right there and then.

Yet here we are, in the year 2009, and the intricacies of PCBs these days make the best planned townships appear appallingly chaotic. The questions beg askance – when you are working with millions of logic gates and switches, each interconnected in their own complex fashion, how do you begin to verify if the circuitry is performing exactly the operations required as per specification? What kind of architecture do you follow? How do you optimize such a vast design for the little bit of space on that silicon wafer? This of course brings us to the domain of CAD and Electronic Design Automation (EDA).

The 22nd International Conference On VLSI Design, held in New Delhi from 5th – 9th January this year saw two groups of researchers from IIT Kharagpur capturing centre-stage at the EDA Software and Design Contest. Under the Software category, Chandan Karfa, Prof. Dipankar Sarkar and Prof. Chittaranjan Mandal of the Department of Computer Science and Engineering bagged the 1st Prize worth Rs. 20,000 for SAST: An Architecture Driven High-Level Synthesis Tool. In the design contest, Prof. D. Mukhopadhyay placed second for High Performance Elliptic Curve Cryptographic Processor for FPGA Platforms; his team was awarded Rs. 15,000.
We are now going to take a closer look at these papers and the technologies they are based on.

More On SAST
High-Level Synthesis (HLS) is the design process of taking an algorithm for a given desired behaviour, say encryption or encoding, and converting it into a hardware implementation; manufacturers can concern themselves with the overall design, leaving the nitty-gritties to the software. As noted by the authors, HLS systems today must be optimal regarding the total size of the hardware, speed, power and other factors. Of crucial importance is interconnections performance – while the connections contribute to 50% of delay in .35 micron technology, it is expected to increase up to 70% in .25 micron technology. The paper presented the concept of an architecture-driven HLS tool to reduce random interconnections.

SAST, or the Structured Architecture Synthesis Tool, allows the designer to finalize the overall architecture of the job at the start of the synthesis procedure, while leaving interconnection to the final stage. Data paths are organized into architectural blocks called A-blocks, each with local storage, a functional unit and a local bus. A-blocks also have access to global buses and memory. The underlying idea is that the data paths are highly reusable and have a regular organization, thus removing random interconnections while giving the designer full control over the final architecture at the same time.

Elliptic Curve Processors

“It is possible to write endlessly on elliptic curves. (This is not a threat.)” -Serge Lang

While gaining notoriety as a formidable component of mathematics, Elliptic Curves have proven indispensable in the world of number theory; apart from applications in cryptography and integer factorization, they play a crucial role in Andrew Wiles’ famous proof of Fermat’s Last Theorem. In their paper, Chester Rebeiro (of IIT-M) and Prof. Debdeep Mukhopadhyay have proposed an efficient implementation of an Elliptic Curve Crypto-Processor targeted for Field-Programmable Gate Array (FPGA) platforms.

Elliptic Curve Cryptography (ECC) has been accepted as a highly secure and efficient standard. Taking the set of all (x,y) solutions of an elliptic curve y2 = x3 + ax + b in a finite field (ie. a field containing a finite number of elements), we find that multiplying an element of the group (our private key) with a curve parameter forms a very secure public key. If we pick a large enough finite filed, reversing this process without the private key involves a computationally difficult dicrete logarithm problem – so much so that a Blackberry operating on a 2.5 V battery can generate a key during a one-second handshake for secure communications that would take all the computing power on Earth thousands of years to brute-force. For a given level of security, ECC has much shorter keys and computational steps than its contemporaries.

FPGAs are devices that can be configured by customers after manufacturing, hence the name “field-programmable”. They possess several logic components, while the interconnections between the logic blocks are decided after manufacture, either by a circuit diagram or code in a Hardware Description language like Verilog or VHDL. This allows customers to wire together the logic to their liking for specialized purposed. From their origins in programmable read-only memory, FPGAs have found extensive application in digital signal processing, aerospace, medical imaging, computer vision, bioinformatics and of course, cryptography. Implementing a cryptosystem requires efficient finite field operations such as addition, multiplication, inversion, etc. Using highly efficient algorithms for addition and inversion, the authors developed a processor on a standard FPGA that showed promising results in several benchmarks.

Have something to add? Share it in the comments.