Ask Slashdot: How Many (Electronics) Gates Is That Software Algorithm? 365
dryriver writes "We have developed a graphics algorithm that got an electronics manufacturer interested in turning it into hardware. Here comes the problematic bit... The electronics manufacturer asked us to describe how complex the algorithm is. More specifically, we were asked 'How many (logic) gates would be needed to turn your software algorithm into hardware?' This threw us a bit, since none of us have done electronics design before. So here is the question: Is there a piece of software or another tool that can analyze an algorithm written in C/C++ and estimate how many gates would be needed to turn it into hardware? Or, perhaps, there is a more manual method of converting code lines to gates? Maybe an operation like 'Add' would require 3 gates while an operation like 'Divide' would need 6 gates? Something along those lines, anyway. To state the question one more time: How do we get from a software algorithm that is N lines long and executes X number of total operations overall, to a rough estimate of how many gates this algorithm would use when translated into electronic hardware?"
Holy crap (Score:5, Insightful)
Either implement it as shaders for a GPU (or a DSP) or hire somebody who actually knows about hardware design if you are hell-bent on implementing an ASIC.
Slashdot: Where *not* to go to get specific advice about specific technical issues.
Why don't they know? (Score:5, Insightful)
You'd think the "electronics manufacturer" would have some idea how to estimate this.
Try Stackoverflow perhaps? (Score:5, Insightful)
I think you may have a better chance of getting an answer if you ask this question on Stackoverflow (or one of its related sites).
Unfortunately, I think asking on Slashdot is only likely to get you some tired and outdated memes / jokes...
They shouldn't be asking you. (Score:5, Insightful)
If they plan on implementing this in hardware, then they should have people who are capable of answering that question. If instead, they are just a manufacturer and aren't capable of doing the actual hardware design, then you have bigger problems than answering this question. That is something you should find out about ASAP.
Completely stupid question (Score:5, Insightful)
The question "How many gates does it take to implement this algorithm?" is stupid. It's like asking "How long is a piece of string?"
There will always be a time/space tradeoff, even with translating an algorithm to hardware. You can save time by throwing more gates at the problem to increase parallelism, or you can save space by reusing gates in sequential operations.
Re:Why don't they know? (Score:5, Insightful)
They do have a way. They asked if it had already been determined.
The correct response is, "We don't know."
software as hardware?! but but but software patent (Score:2, Insightful)
Clearly it's not possible to render a software program as hardware. If everyone who explained the process (use Verilog) above is correct, that would mean that the exact same algorithm exists as both hardware and software.
We can't have the same algorithm exist as both hardware and software, because that would mean algorithms are hardware just as much as they are software.
that would mean all the people whining about "software patents" may as well be whining about unicorns. I hereby declare Verilog, ASICs, and FPGAs to be non-existent so we can continue to pretend that there is such a thing as a "software patent".
It's an optimization problem (Score:5, Insightful)
You already have your algorithm running in electronic hardware, right?
Your current gate count is the sum of
* the gate count of your CPU
* the gate count of your RAM
* the gate count of your program ROM
So that's an upper bound on the gate count.
If that number is too big for your manufacturing partner,
then you have an optimization problem.
Optimization is a hard problem...
The key to success. (Score:5, Insightful)
Re:Holy crap (Score:5, Insightful)
Just 'fess up and say "We don't know, we're software people, not hardware people".
If it's really important they might offer some help.
Knowing The Algorithm Is NOT Enough (Score:5, Insightful)
Knowing what algorithm you want to run in hardware in not even close to enough to estimate gates. You need to know the algorithm, and the required performance, and have a sketched out HW design that meets those goals. THEN you can estimate gate count.
For a simple example of why this is, consider processors. A 386 and a Sandy Bridge i7 implement very similar "algorithms" - it's just fetch->decode->execute->writeback all day long. If you implemented them in software emulation, it would be very similar software with some additional bits for the newer ISA features on the i7. But a 386 is about 280 THOUSAND gates, and the i7 is about 350 MILLION gates/core - three orders of magnitude different. Of course, there's at least a 2 order of magnitude performance difference too - it's not like those gates are going to waste.
Point is, knowing the algorithm isn't enough to get even a finger in the wind guess at gate count. If you need an answer to this question, you need to get competent HW design people looking at it.
Re:Holy crap (Score:5, Insightful)
This is the only sane answer. They probably only asked to find out if you happened to know.
Say you don't know, and let them look at the code to figure it out.
Re: Verilog (Score:5, Insightful)
I still must disagree. Yes, the syntax is somewhat like C. However, WHAT you are coding is completely different. In particular, things that C and do with a simple "if" statement are not allowed at all in proper gate design. It is not hard to imagine a software guy coding latches all over the place, assigning the same signals from withing different always blocks, etc. Even "always @(posedge clock)" may be a fundamental paradigm shift for a software guy. And not to mention the rather arbitrary way that Verilog treats wire vs. reg.
wire a = b & c;
wire a;
assign a = b & c;
reg a
always @(*) a = b & c;
These three constructs do the same thing. Why is one "wire" and one "reg"?
What is the difference between the two blocks (they are NOT the same - blocking vs. non-blocking)?
always @(posedge clk) begin
a = b;
c = a & b;
end
always @(posedge clk) begin
a = b;
c = a & b;
end
What about race conditions? Glitches on combinatorial logic? Proper coding of state machines? Need memory? How do you drop in an encrypted 3rd party DDR controller and PHY? Interface with AHB bus? In a given process, how many levels are logic are reasonable for a given clock speed? What exactly are hold violations?
I am not saying that any of these are insurmountable. What I am saying is that a good digital designer is worth paying for, and a software guy may have a very steep learning curve indeed.
Re:Holy crap (Score:0, Insightful)
This is the only sane answer. They probably only asked to find out if you happened to know.
Say you don't know, and let them look at the code to figure it out.
Anybody who holds an actual 4-year CS degree should be able to do at least a rudimentary analysis of this type.
Anybody who holds an actual 4-year "triple E" degree should be able to do a full blown analysis.
Obviously neither company has any employees with either of those two degrees working for them. Or if they do, they really suck.
Since submitter admits they are a software only house, my personal advice is to go find a different company to handle the hardware.
Comment removed (Score:4, Insightful)