Thursday, August 23, 2007

Treemap Widget in Dojo GFX

Last week I was working on implementing 'bin packing' algorithm and visualizing output on 2D plane, using DOJO toolkit. At the time of this post it's available here:

It shows categories of footprint and descendant items. Implemented in dojo gfx (SVG/VML).

Some information on bin packing:

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media.

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires O(n log n) time. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.


Got an idea to use the treemap widget in Ganglia project.
It contains two rationales:
a) use treemap to visualize metrics, so it is more compact and doesn't poll every X amount of time.
b) use client-side code to render readings and be more compact way to display multiple parameters

In the following demo I used dojo toolkit (version 0.9) and php:

Dojo's SVG support is still experimental though (i think it is a wrapper interface for both SVG implementations).

I'm planning on implementation of another approach which uses curves instead of rectangles (based on Voronoi tesselations).

Sunday, August 5, 2007

How to install Attansic L2 Network Driver in Fedora Core 7

Having bought new box for my kids, I've got ASUS P5GC-MX motherboard with Intel chipset and installed Fedora Core 7 (Live CD).

All worked fine except integrated network card from Attansic (Taiwan). First of all, I couldn't figure out what type of device I have, there were two Linux drivers provided: L1 and L2.

A little bit of googling and voila - it's L2 !
As it happened, the driver required building Linux kernel module (responsible for network) as LiveCD install didn't have it by default.
What ?!
Building kernel module ? Hmm... (why don't I just install windows, I asked myself several times during this procedure :) )

My default method to install all the required components is yum, but it was useless without network setup. So I had to download all packages to my another desktop, copy them to USB key and then use the key at target Linux box.

You would need to get kernel-headers-2.6.21-1.3194.fc7.i386.rpm, kernel-devel-2.6.21-1.3194.fc7.i686.rpm, gcc with dependencies
- glibc-2.6-3.i386.rpm,
- glibc-headers-2.6-3.i386.rpm,
- libgomp-4.1.2-12.i386.rpm,
- glibc-devel-2.6-3.i386.rpm,
- gcc-4.1.2-12.i386.rpm,
- cpp-4.1.2-12.i386.rpm,

and install it using RPM (e.g. rpm -Uvh _name_here.rpm).

To verify that you are ready to build kernel module, check content of /usr/src path, it should contain 'kernels' directory.
Now follow instructions and change current dir to /src/ dir with driver source code and do:
'make install'.

I had some issues with drivers provided on motherboard CD, as happened it was outdated version something like It complained on missing config.h etc

After some googling, I figure out, that version is for older kernels (before 2.6.21). Then I found newer version of the driver and got rid of config.h and other header errors, but got another ones about non-declared members of
struct. A short look at C code showed that some debugging parts are excessive, so simple commenting did the trick.

At this point I'd ran 'make install' , then 'cd /lib/modules//kernel/drivers/net', 'insmod atl2.ko' and got network device working. Then I went to Network configuration and added ip address and dns information.
After device activation I was able to browse internet.

Newer version of driver is (was) available here:

RPMs are available at

Good luck !

ps. also found this site (it has Linux Drivers package, but download was so slow that i didn't test the package)


When applying updates that include kernel updates, after reboot it loads new kernel and module we built is not loaded, so no network would be available. In my case I just edit grub.conf and set old kernel (the one we build driver for) and reboot.

Cloud Computing Google Group