Urgent Help for xilinx Synthesizing

[c***@gmail.com]

Hi Friends

Friends, i have been struggling for 1.5 months on a problem.Let me
explain u a little bit.

I am working on FPGA implementation of Dijkstra's Shortest Path
Algorithm on XILINX 7.1 ISE.Now I hav implemented the code in
verilog.The Number of nodes in my case is 256(IF U REQUIRE MY CODE I
WILL SEND IT).The tragedy is that the code is working fine but when i m
synthesizing it it is giving the following error which i am unable to
resolve.

The error is "
Portability:3 - This Xilinx application has run out of memory or has
encountered a memory conflict. Current memory usage is 1869512 kb.
Memory problems may require a simple increase in available system
memory, or possibly a fix to the software or a special workaround. To
troubleshoot or remedy the problem, first: Try increasing your system's
RAM. Alternatively, you may try increasing your system's virtual memory
or swap space. If this does not fix the problem, please try the
following: Search the Answers Database at support.xilinx.com to locate
information on this error message. If neither of the above resources
produces an available solution, please use Web Support to open a case
with Xilinx Technical Support off of support.xilinx.com. As it is
likely that this may be an unforeseen problem, please be prepared to
submit relevant design files if necessary.
ERROR: XST failed"

My verilog code consists of following operations:
1)Calulating the adjecancy Matrix and Path Matrix.
2)Recursive Algorithm using Task (Palnitkar says that Task and Function
is Synthesizable).

Also let me inform u that my code is 100% behavorial.

While synthesizing It shows "Enabling Task " for 8 hrs and then shows
above error.
If u know anything about the above error please tell me as the deadline
is approaching fastly for project submission.

Looking for ur help
Thanx
Saroj
mail me at:***@gmail.com

[h***@yahoo.com]

What size is your Dijsktra's instance? 256 graph vertices? Try smaller
graphs. See if "8 hrs" varies accordingly.

From my old knowledge Dijsktra's algorithm complexity is O(n^2) which

means it must have two nested loops.
How have you implemented them in your HDL? Do you instantiate 256^2
something in your code?

Good luck.

Hrh.

[Chauhan]

Thank you very much
Yes friend my graph consists of 256 vertices.I am having 3 main part of
my algorithm:
1)Adjecancy matrix(size=256*256)
2)Path matrix(size=256*(256*4)..4bits for allocating distance form
other nodes)).
3)Recursion.
The Complexity may vary from O(n^2) to O(nlogn).
If you need my code i will send you.

I will try your suggestion by reducing the number of nodes to 8.

Also You are absolutely right that my recursion requires 2 for loops.

Now how i have implemented?
1)Let us take a squre grid of size 4*4.Number the nodes from 0 to 15.
2)Nodes 0 to 3 are in 1st row,4 to 7 are in 2nd row and so on.
3)Suppose 0th node is the Source node and say any node..12 is
destination to reach.
4)I have been provided the information that which node is behaving as
obstacle(the cost to reach to the obstacle would be higher than the
normal ones).
5)So my 1st task is to find out the neighbors of each and every node
and costructing the adjecancy matrix accordingly.
6)Similarly I compute the Distance(cost) of each node to its
neighbouring nodes(if normal node(connected)..distance=1,if connected
but obstacle..distance=say 15,if not connected..distance=25698(a large
no.)).

This completes my graph information.
Now I store the above into a memory of required size(for adjecancy
matrix 16*16 and for Distance matrix (16*64).

After that i just implemented the recursive algo to get the path and
stored the path(the Parent node to each node) in another memory.

Still if you need clarification you can take my code.

Thank you once again

[c***@gmail.com]

Your problem may not be with your code or implementation but with the
synthesizer fitting the behavioral code into the technology with the
amount of resources your system has?
What are the system specs of your workstation and what Xilinx part are
you targetting?

[h***@yahoo.com]

I still recommend to change the size of your instance (from 256) and
see what happens.
Notice, the complexity of an algorithm is always the worst-case, so it
is O(n^2).

Also, you cna change the size of your FPGA (switch to a bigger one) and
run it again and see how it behaves. You don't need to program the
bigger FPGA though, just see how it behaves in a bigger FPGA.

Regards,

HrH