cyplayer.com

Quest for Imperfection

I decided to dabble with my culinary skills today. I made the north Indian delicacy, Cholae (garbanzo beans). I took my job pretty seriously, adding the thousand five hundred (kidding) ingredients at the right time, and in right proportions. So, when the stuff came to a boil, it was time to taste it to confirm that everything was OK. I had to do the tasting twice before convincing myself everything was ok. However, the whole process threw open a few questions which people might experience in their professional lives. The cooking part can be related to the “development” of a product, and the tasting part can be related to the “verification” of the product. Take the semiconductor industry for example. This industry is consumed by the need for verification. The time it takes to verify a product far exceeds the time to develop the product in the first place. Every second year, a new standard emerges. While, development has mostly been limited to Verilog language, verification has gone from C++ to systemVerilog to VMM to OVM to you name it.

So, how much verification is too much verification? In the kitchen parlance, when should I stop tasting the food? If I search for eternal quality, I might continue tasting the food until I have either consumed all of the food, or it is well past dinner time. On the other hand, I could do it just once, make some changes to my preparation and call it done. The former approach will ensure nobody gets food. The latter approach will ensure everyone gets bad food. The end result in both cases is the same: hungry and angry people. Similarly, over-verification delays the product’s time to market, making it essentially useless. Under verification causes production stops, which again hits the company’s schedule, and its reputation in the industry takes a nose dive.

The key to successful products is to find the right balance to ensure that the end product is excellent, but not perfect. The quest for perfection is like the 80-20 rule. It is relatively easy to get the product to 80% quality, but the last twenty percent becomes progressively harder. So, a 95% product quality may be acceptable to most customers, and achievable in reasonable time. Depending on the type of product, spending time over the last 5% may not be cost efficient. On the other hand, enough effort must be spent to get the product from 80 to 95%. If this is not done, the product may not be usable.

In kitchen parlance, a lot depends on what I do with my first tasting. Depending on how well I analyze the taste, I can make a significant progress between the first and the second tasting. A dumb me would just add salt, only to realize later that I added too much salt. Then I would add something else to neutralize the salt and end up running in circles. The smart me would analyze the amount of salt required, and also realize that certain ingredients are missing. I would add them in the right quantity, and by the time I taste again, my dish would have improved significantly.

Similarly, a verification engineer can choose to be dumb or smart. A dumb engineer usually would come back with a one line statement that reads “code crashed on line 1293”. The developer would go back, fix the problem and send the code back to the verification guy. His second report would read “code crashed in line 1324”. Now, when the code at 1394 is fixed, it would crash on line 1293!!! The code would be ping-ponged between the developer and the verification engineer, until the developer, verification engineer and the manager are fired for not releasing the product on time. The smart verification engineer will read the architecture specification and will have full knowledge of the product. He will understand the root cause of the problem, and provide as much details as possible to the developer. The developer will then fix many problems in a single iteration, thereby reducing his workload, as well as that of the verification engineer. I wish life were so easy!!!

The Book-shelf Organization Problem

Today, I embarked on my annual project of re-organizing my book shelf. Over the years, I have collected a whole lot of books, organized my shelf a few times, and actually read very few of them. Most of the books in my collection are technical in nature, spanning the realms of Computer Science and Electrical Engineering.

While I was in the middle of the re-org, I found myself solving the familiar problem of packing as many books as possible in the amount of space that the shelf offered. This falls in the category of what is known as Knapsack problem in Computer Science. The problem has a common occurrence in many aspects of Electrical Engineering and Computer Science. When we try to pack blocks of logic in a semiconductor chip, we would like to do it as efficiently as possible. In other words, we would want to pack as much as possible in as little as space as possible. Similarly, when operating under constrained memory, storing data blocks of different sizes in the memory also has a similar requirement: try to store as much as you can in as little a space as possible.

Packing identically sized books in my book-shelf would have been pretty simple. I would just stack the books one after the other until all the space in the shelf is taken up, or all my books have been stacked. But not all my books are of the same size. I have this computer architecture book which is humongous and at the other end, I have a book on functional analysis that would fit in my pocket. So, the problem is to figure out the best order of stacking these books so that I can get the best possible result. Mathematically, I will formulate the problem as follows:

Assume I have N books in all, and book B(i) has a size S(i). I would like to maximize the number of books I stack up, which also means that I want to minimize the number of books that were left at the end. Let X(i) denote a variable that is set to 0 if book B(i) was not stacked, and 1 if the book B(i) was stacked. So, the formulation will be:

Maximize Sum(X(i)) under the constraint that Sum(X(i)*S(i)) less than or equal to the size of the shelf.

Now, Knapsack problem has been proved to be NP-Hard. What it means for the layman is that unless you think you have a serious shot at Nobel Prize, statistically speaking, the odds of you finding an algorithm that will optimally solve the knapsack problem in polynomial time is less than 0.000000000000000000000001. In other words, convince yourself that you have nothing better to do before trying to find an optimal solution to the problem. However, brilliant minds have done us a favor and found several solutions that are pretty close to optimal, if not optimal. Fortunately, many of these approaches is simple to implement.

The knapsack problem becomes complex when I also want to ensure that I arrange the books in such a way that I spend less time searching a book when I want to read one. Now, not only do I have to think about maximizing the utilization of the space, I have to make sure I can get to the book as soon as I can. How do I do that? If I were to draw a parallel from computer science, the concept of caches comes close. Data is organized into sets to make search easier. This is similar to me organizing my books into racks, with each rack organized into a separate category. This is not rocket science. We have done it in libraries forever. But then, this considerably reduces the number of books I can stack in the shelf. My books on computer architecture, PCI standard etc took a lot more space than all these math books which were comparatively small. Now, this opens a whole lot of opportunities for optimization, where the relative ease of search versus the efficiency of space utilization becomes more of a choice than an exact solution. I got my books stacked using some adhoc algorithm created on the fly. I am still looking for a better solution from what I came up with.

Sonics AMBA Interconnect

On-Chip Interconnect has grown in complexity and their importance in the past decade. Typical systems incorporate a bunch of processing and memory elements on the chip. SoCs are increasingly incorporating more number of cores to enable better performance at lower frequency and better power management. Therefore, what was a “front side bus” to establish communication between a CPU and the memory controller is increasingly being replaced by a “front side interconnect” in the SoC world. With increasing complexity in the chip, it is proving lot easier for chip designers to integrate a standard based interconnect onto the chip, rather than designing the interconnect themselves.

Companies like Sonics have cashed in on this opportunity and have been selling on-chip interconnect solutions for a while now. The on-chip interconnect market has brought with it two competing standards as well: OCP and AMBA. AMBA in turn comes in different flavors namely, AXI for high performance, AHB for lower performance and APB for peripherals. So, in effect, we may have a chip designer with a bunch of OCP cores, a bunch of AXI cores and a bunch of AHB cores and it can be a pain in the neck to design an interconnect that is good enough for the performance requirements of the chip and more importantly, is scalable and area efficient.

Sonics recently launched a product called SNAP. Traditionally an OCP house, SNAP is the company’s answer to AMBA protocol. In fact it is much more than just AMBA. The cool thing about SNAP is that it is web based and can be downloaded from SNAP Download . And it is free to evaluate. So, you can download, create a design and submit to the Sonics server that will in turn generate the RTL code for the interconnect, send it back to you. You can then simulate your system all for free. SNAP has been designed to seamlessly integrate OCP and AMBA compliant cores. Moreover, it incorporates the concept of layers and branches. They provide the users the ability to model the interconnect hierarchically so that they are able to minimize area, and at the same time operate at high performance. Finally, SNAP comes with power down support. The user can choose to power down the interconnect, the cores, or both depending on the current state of traffic in the system. The website also has some pre-configured SNAP designs that you could use as a starting point. All in all, it is a “cool” (pun intended) product for cool SoCs.