On 10/20/06, tsuraan <[EMAIL PROTECTED]> wrote:
How would you express a recursive algorithm in Verilog? For example, a recursive factorial in C isint factorial(int i) { if(i == 0) return 1; return i*factorial(i-1); } Can this be done in Verilog?
I don't actually know if you can synthesize recursive function calls in Verilog. I'm sure you can do it in simulation, but simulation is an abstraction. Recursion is basically nesting of the same function call to an arbitrary degree. Everything has to be fixed in hardware, so you would need to set a recursion limit, and I'm not sure how you would do that. This, I think, is a case of trying to be clever with the language, where actually, we need to be clever with our designs and then represent them straightforwardly in Verilog. So, what do you want to do? Design chips, or write Verilog code? The bottom line is that whatever you might want to describe recursively, you're better off describing as a loop or an explicit state machine. Design a state machine that has a stack, and you have what's called a push-down automaton (PDA), something that can process context-free languages. With this, you can make a straight-forward implementation of many recursive algorithms.
Of course, it's generally wise to convert recursive algorithms in C to explicitly iterative ones to avoid stack overflow, but sometimes it's just easiest to express things factorially. Can that be done in Verilog? I suppose you'd have to create some stack (ring buffer?) to store your previous data and always use that?
Forget the word "Verilog". That's like asking if the same algorithm can be implemented in both C and Pascal. Yes, it can be. But you have to characterise the problem appropriately to the context. You're used to writing software that has a dynamicity that doesn't come for free with hardware. So, yes, given logic for a stack and a state machine for the computations, you can do exactly this. But we probably wouldn't call it "recursion". We'd call it a PDA. It you had two stacks or ring data structure, you'd have something more like a Turing machine. Notice how here, you have to expose all of the mechanisms that you take for granted in software. Recursion is a nice abstraction, but what it really means (in software) is that you have a stack, and when you do it in hardware, you have to explicitly implement that stack.
The reason I ask is because I'm working on a pixel-perfect cubic bezier curve rederer, and once it's done in C I'd like to try doing it in Verilog, but I have no idea how to express my recursive algorithm in hardware. TrueType fonts use bezier curves, so I figured it would be cool to have the ability to accelerate them in hardware :)
You COULD try to reimplement that algorithm. But to get efficient hardware, you'd probably want to reexamine the whole problem from the ground up. Flatten it completely, and turn sequential code into state machines and pipelines. _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
