ON CHIP GRAPH MEMORY USAGE APPROXIMATIONS FOR VIRTEX 6

ON CHIP GRAPH MEMORY USAGE APPROXIMATIONS FOR VIRTEX 6

1. constants value = 4 bytes
2. op nodes received flag = 2 bits each (00 - no inputs, 01 - 1 received, 10 - all received, 11 - ready to be sent)
3. all nodes node id = 2.125 bytes
4. each edge = 3.125 byte


0.3n*4 + 0.7n*0.25 + n*2.125 + 1.25n*3.125 = 37*1024*1024
1.2n + 0.175n + 2.125n + 3.90625n = 37*1024*1024
7.40625n = 37*1024*1024
n = ~5 million nodes

0.3n*4 + 0.7n*0.25 + n*2.5 + 3*1.25n = c
(1.2+0.175+2.5+3.75)n = c
7.625n = c
sequential base case fits less nodes...

hamm...
1. constants = 5.1m x 4 = 20.4Mb
2. 9.7m x 0.25 = 2.4Mb
3. 14.8m x 2.125 = 31.45Mb
4. 19.4m x 3.125 = 60.625Mb

Required = ~110Mb

hamm...seq.
1. 4.3m x 4 = 17.2Mb
2. 7.6m x 0.25 = 1.9Mb
3. 12m x 2.125 = 25.5Mb
4. 15.1 x 3.125 = 47.1875Mb

Required = ~88Mb