I need to implement a faster version of BFS. I am looking for a new representation for the graph. I am going to assume that the cacheline size is 64 bytes on my Turion 64 X2 processor. It should lead to higher reference of locality and much better packing than before. And if my assumption of cache line size turns out right, it's going to be a big plus.
I have a new idea in mind, but I need to figure out the nuts and bolts for it. Hopefully should be done soon.