Night Fox of New Jersey

The movie Ocean's Twelve featured a very interesting character called "The Night Fox", a master thief enacted by the French leading man Vincent Cassel. In that movie, Cassel steals the Coronation Egg (in fact it's fake) by acrobatically avoiding the laser beams. In its previous version, "the Amazing Yen" uses his acrobatic skills to rob a casino. I thought such things are possible only in movies.

I was wrong. In New Jersey, a band of acrobatic thieves managed to rob Best Buy in a similar fashion. The thieves never appeared in the security camera. The entire floor had sensors, but still no alarm was tripped, as the thieves never stepped on the floor. Apparently they left boot print on the gas pipe they climbed by. NJPD is looking for the thieves.

Job in 2018

The unemployment numbers frustrate me and I feel we have to be like this for a long time. Oh.. Light at the end of the tunnel. A new study makes a convincing argument that by 2018, there will be overwhelming number of jobs open because of the mass retirement of baby boomers. And this is of course with no change in the immigration policy or labour law. Just eight more years! At that time, inflation may sky rocket and it is something to worry about. Poor policymakers - there is always something in the economy that spoils their sleep at night.

Where is consumer electronics heading?

Here is a graph by International Data Corp. that indicates where we are heading in the consumer electronics market. People want it small and want it to connect to the worldwide web!

Picture = 1024 words

Most of the time, I need a pictorial representation of call graphs to understand the profiler information with more clarity. Usually I use it to ensure that I am using the memory and CPU efficiently and which part of the code I need to optimize to get the best bang per buck. In my laptop, I use valgrind to generate the call graph and KCachegrind to study the visual representation of call graph. When I use Solaris, I use the dtrace script given by my friend here along with graphviz to visualize the call graph.

But recently at work, I got a Fedora system for which I was not the system administrator. The system administrator was reluctant to install valgrind or KCachegrind stating the fact that gprof was installed in the system and I could use that. Only thing I dislike about gprof is the fact that I have to recompile my C source codes with an additional option. But other than that, I have nothing against it. Even then, I needed a visual representation and so I started writing yacc and lex to parse the gprof output and create a graphviz file. Before getting deep into it, I noticed that there is something called gprof2dot - a python code that converts gprof output to a dot file.

gprof2dot does the magic that I wanted. Interestingly, it has support for an array of profilers including valgrind. The source code is open and it is object oriented and well organized. Each profiler is parsed by a separate class (like GProfParser) that implements a common Parser class. So we can easily plugin our code for our profiler's output (if we use a different profiler). Only thing that could have been done differently is that the author could have used GvGen dot file generator library instead of creating it as a generic output file.

Now all I need to do is to use gprof2dot to generate the dot file that I can parse through graphviz. Or alternatively I can modify the source code to use PyDot library and generate the PNG file in a single shot. Once again the world is saved by free and open source software!

Bloom Box and Artificial Photosynthesis

A couple of weeks ago, CBS' 60 minutes focused on K.R. Sridhar's innovation, the Bloom Box, a small sized wireless power plant that can generate energy for your house. That's a form of clean energy. We can envision that in the next 10 years, all homes would supply electricity for themselves with the Bloom Box that I looked at as the miniature of a monolith (Tycho Magnetic Anomoly-4!).

Now Dan Nocera of MIT made an absolutely remarkable innovation that artificially mimics photosynthesis. Dr. Nocera has created a catalyst that uses sunlight to convert water and carbon-di-oxide into hydrogen and oxygen, in a project funded by ARPA-E, which in turn was funded by the stimulus package. The generated hydrogen and oxygen can then be recombined in a fuel cell to produce energy. Please look at the embedded video.



These innovations are impressive. However I don't know whether they can produce clean, sustainable energy at industrial scale at a low cost. Many of the clean energy companies face this problem of huge production cost and problem with production in scale. If one or both of these technologies work, they can be the Holy Grail for all our energy crisis (both present and future). Who knows? May be they can be fitted in automobiles, like cars, trains and planes to operate them without wasting the fossil fuels and without polluting the environment. Great independent work by Dr. Sridhar and Dr. Nocera and more importantly their teams! Hats off!!

UPDATE: You can watch the CBS' coverage of K.R.Sridhar's Bloom Box here. Sorry, I cannot embed that video.

Compiling the extra dimension

Three dimensional FPGA and three dimensional chips are creating a lot of buzz and may be the direction that VLSI design and reconfigurable computation are headed in. Why is it just a "may be"? There are a few start up companies that have come up with the 3D fabric and the interesting part is that the third dimension is not the same for everyone. In some architecture, the third dimension is the z-axis. So the 3D FPGA is just multiple fabrics of FPGAs stacked up. So the chip that looked like Manhatten structure earlier would start looking like Tokyo flyovers with roads running between different layers. In some other FPGA architecture, the third dimension is the time axis. What all these essentially mean is that, a mash-up multi-dimensional FPGA is certainly a possibility. So what's the problem with this?

Starting up a company with a new FPGA architecture and be successful with that is extremely difficult. The reason is not because of the quality of your architecture; rather it is because you may have to make the entire array of computer-aided design tools available to make your architecture programmable. Every company that might potentially use the newly introduced architecture would have a tried and tested development process that is strictly defined on the basis of the existing technology. They would want to fit the exact process with the new technology and this is where several newbies fail. Unless you can convince your customers that the benefit that your new technology brings to the table can overwhelm the temporary loss of productivity due to the process change, you cannot sell your product.

So the three dimensional FPGA should have a HDL parser and optimizer, logic minimization, technology mapping, placement and routing tooling support to the same extent that Xilinx or Altera provides. Now the first two are pretty established and architecture independent. You can use one of the different implementations of Espresso for logic minimization. Technology mapping can be very much similar to how it is done in the existing 2D FPGA, using force directed scheduling or any other established scheme.

The problem starts with the last two: placement and routing. Most of the placer and router used in industry are proprietary. I am pretty much confident that Altera's placement algorithm is deterministic and may be Xilinx also has a deterministic placement, I am not sure. When it comes to routing, most of these tools use negotiated routing with the negotiation scheme being proprietary. Placement is a NP-hard problem and routing is NP complete. So to achieve a critical path, if your placement and routing takes twenty times more CPU cycles than what the existing tools take, then your potential customers are going to take a step back immediately. Well, they want a "rapid" prototyping, you see.

If the 3D FPGA happens to be entirely made up of similar CLBs and IO blocks, the placement and routing is a little easier. Versatile Place and Route (VPR) is the standard, open source academic tool for placement and routing. It performs a simulated annealing based placement and Pathfinder-based negotiated routing on array-based FPGAs. How easy is it to modify VPR to support the third dimension? A block is defined in VPR through the following structure:

struct s_block
{
char *name;
t_type_ptr type;
int *nets;
int x;
int y;
int z;
};

In this structure, you can give the name of the block, type of the block, typically CLB or IO-block and the cartesian coordinate of the block's location, during placement. Here the x and y indicate the coordinates in x-y plane. What is z? No, it's not the third dimension you are looking for. Rather z is the number that specifies which sub-block the net refers to. So a single block can have multiple sub-block - each sub-block is a logic element. In this structure, you may have to add another variable to specify the coordinate in the third dimension (you may have to use a different name, since z is taken). And then it involves changing all the loops in VPR. You may also need to change the placement file's structure to introduce the extra dimension and make Pathfinder understand that. It is difficult; but with some effort, it is possible to make VPR support the 3D FPGA placement and routing. But can its quality compete with the existing 2D FPGAs? Can it be done on click of a button at a reasonable speed?

So on summary, introducing the third dimension in FPGA is certainly impressive. But if you want to make money out of it, you have to provide an array of necessary tooling support so that your potential customers can realize the fruits of extra dimension, without taking much risk and paying much price. On the other hand, 3D FPGA may evolve from some already established company that is not struck in a marketing myopia. Lets wait and see.