Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Ask Slashdot: How Many (Electronics) Gates Is That Software Algorithm?

Soulskill posted about 7 months ago | from the somewhere-between-zero-and-lots dept.

Hardware 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?"

cancel ×

365 comments

Sorry! There are no comments related to the filter you selected.

Holy crap (5, Insightful)

CajunArson (465943) | about 7 months ago | (#45901087)

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.

Re:Holy crap (-1)

Anonymous Coward | about 7 months ago | (#45901199)

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.

And to think, they rejected my Ask Slashdot submission on how to find a cheat code on my bank's web site for unlimited moneys, so they could greenlight this shit. Never before has an ask slashdot been so "please do my job for me" and i've seen some doozies. It would be like a contractor going online and typing "how many nails will i need to build this house?" WTF?

Re:Holy crap (0, Flamebait)

AJH16 (940784) | about 7 months ago | (#45901259)

Getting unlimited moneys is easy, just make a big enough bank, take all the money and then tell the government you need more.

Sounds like a joke (4, Funny)

Cryacin (657549) | about 7 months ago | (#45901289)

How many Gates will it take to implement your software project?

One. His name is Bill, and here is yours.

Re:Holy crap (5, Funny)

Megane (129182) | about 7 months ago | (#45901519)

And to think, they rejected my Ask Slashdot submission on how to find a cheat code on my bank's web site for unlimited moneys

Just walk up to any ATM and press: up up down down left right left right B A start.

Liar! (2)

nobuddy (952985) | about 7 months ago | (#45901579)

I just tried this and all my money was transferred to a different account.

Re:Liar! (0)

Anonymous Coward | about 7 months ago | (#45901679)

Thank you for your (not so) generous donation.

How many (2, Funny)

Aighearach (97333) | about 7 months ago | (#45901097)

beowulf clusters does your algorithm desire?

Verilog (4, Informative)

tepples (727027) | about 7 months ago | (#45901099)

If you learn to program in Verilog, you could try synthesizing for some FPGA and see how much space it takes up on the FPGA. But then programming for an FPGA differs from programming for a serial computer in that each line of code runs essentially as a separate thread, usually triggered on another signal (such as a clock) having a positive or negative edge.

Re:Verilog (5, Interesting)

Anonymous Coward | about 7 months ago | (#45901223)

if you only need a estimation, use something like bamboo from PandA to convert your C Code to Verilog. Then synthesize this code for a FPGA. In the summery you should find how many logic cells would be used as well as how many digital gates in an asics are necessary. This value is only a estimation, but for your question, this should work.

Re:Verilog (5, Informative)

ranulf (182665) | about 7 months ago | (#45901541)

The number of slices or logic cells or whatever else a particular synthesis program for a particular chip generates doesn't exactly correspond to a number of gates either. For instance, a single 4-in 1-out LUT on a Xilinx can be used for 1 gate or 6.

I wouldn't have much confidence in automatic C to HDL conversion either. Good HDL design is about understanding the problem in terms of gates and parallelism. FPGAs and ASICs in general aren't particularly good at things that CPUs are good for, and inversely CPUs aren't especially good for things that FPGAs and ASICs can do well.

The OP shows such a lack of understanding of hardware design that it's not funny! "Add = 3 gates, Divide = 6 gates" is quite comical to anyone who actually knows these things. A more ball park is that an n-bit add can be done with 2n LUTs, in terms of gates it's about 5n gates, but really that depends what gates you have available. A multiplier is massively more, dividing is even more complicated still. Fortunately, many FPGAs come with a few dedicator multipliers... Unless your algorithm requires only as many multipliers as you have available, you're probably best building a state machine and multiplexing a single multiplier unit, in much the same way as a CPU multiplexes the ALU at its core.

The whole thing is massively dependent on algorithm and experience of the person doing the porting. The best advice is to say "I don't know" or to hire someone who does or suggest them running the algorithm on an embedded CPU.

Re:Verilog (3, Interesting)

Andy Dodd (701) | about 7 months ago | (#45901369)

While there are some compilers that ATTEMPT to convert C/C++ into a hardware representation - These will usually fail unless you understand the target hardware.

http://www.drdobbs.com/embedded-systems/c-for-fpgas/230800194 [drdobbs.com]

One thing is: Even if you can successfully compile from C to Verilog or VHDL, there is no guarantee that the Verilog or VHDL will successfully synthesize on your target hardware.

Even if it successfully synthesizes, there is no guarantee that it will be in any way an optimal implementation.

Some C algorithms may never transfer well into a hardware implementation.

Re:Verilog (1)

bob_super (3391281) | about 7 months ago | (#45901665)

This.

But there has been recent progress, and Xilinx is pushing hard to get people to compile C to gates with their Vivado HLS (guess the targets?).
Worth having a look at, since you usually can get a 30-day eval license for FPGA tools.

Why don't they know? (5, Insightful)

Anonymous Coward | about 7 months ago | (#45901101)

You'd think the "electronics manufacturer" would have some idea how to estimate this.

Re:Why don't they know? (5, Insightful)

janeuner (815461) | about 7 months ago | (#45901231)

They do have a way. They asked if it had already been determined.

The correct response is, "We don't know."

Re:Why don't they know? (1)

i kan reed (749298) | about 7 months ago | (#45901233)

Because manufacture doesn't necessarily mean design expertise?

Warning: Car analogy inbound.
Why can't the workers on the assembly line of a GM plant design a car?

Re:Why don't they know? (3, Funny)

Sarten-X (1102295) | about 7 months ago | (#45901581)

Because they're robots with no AI functionality?

Re:Why don't they know? (3, Informative)

Megane (129182) | about 7 months ago | (#45901599)

A more accurate car analogy would be GM wanting to build a car using your technology and asking you how many assembly line workers it would take.

Re:Why don't they know? (1)

AndyKron (937105) | about 7 months ago | (#45901653)

I'm thinking the "electronics manufacturer" doesn't have an idea, or they wouldn't have asked that question.

Just like any other software project (5, Funny)

mbadolato (105588) | about 7 months ago | (#45901107)

Make up a number, then when they complain that it was way off, blame it on their management changing scope a hundred times throughout the life of the project!

Re:Just like any other software project (1)

Anonymous Coward | about 7 months ago | (#45901295)

42!

meh (0, Troll)

Anonymous Coward | about 7 months ago | (#45901123)

This is the dumbest ask slashdot ever. Give them the source code and tell them to figure it out. Remind them they are the EEs. I don't know which of the two companies here is stupider.

C to HDL to netlist (2, Informative)

Anonymous Coward | about 7 months ago | (#45901131)

As a first-order approximation, you can translate your C/C++ code to a hardware description language (HDL) such as VHDL or Verilog. Tools exist for this process. The result won't be optimized for the peculiarities of HDL, but it will provide a good start. From there, you can port the HDL to a Xilinx or Altera FPGA netlist using vendor-specific tool chains. The porting effort will summarize the logic and memory resources of your implementation. Any digital hardware engineer worth their salt should be able to translate FPGA utilization metrics into whatever platform they are interested in.

Try Stackoverflow perhaps? (5, Insightful)

Anonymous Coward | about 7 months ago | (#45901147)

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. (5, Insightful)

pavon (30274) | about 7 months ago | (#45901151)

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.

Cost estimate (1)

tepples (727027) | about 7 months ago | (#45901193)

Maybe they can do the translation, but they need a number for how many gates so that they can give a number for how many dollars.

Re:Cost estimate (0)

Anonymous Coward | about 7 months ago | (#45901405)

I'm not sure if the economics are so straightforward.

I've seen many designs where a PIC has been used, where the same job could have been done with random discrete logic. It was cheaper to use a PIC, as it simplified the design and testing process, even though the part cost was higher and many thousands more gates used.

Re:Cost estimate (2)

EndlessNameless (673105) | about 7 months ago | (#45901485)

If they can design the hardware, they can ask for the source and supply the quote themselves.

If they can't, then OP needs to understand they have no practical design capabilities and plan on paying someone else to design it---before paying these guys to manufacture it. Or he can search for a shop that can handle both the design and the manufacture.

Re:Bingo (0)

Anonymous Coward | about 7 months ago | (#45901677)

Go to a hobby site about EE learn about tools they use. Slashdot use to be is SE site...

Minecraft (5, Funny)

nbetcher (973062) | about 7 months ago | (#45901157)

Develop out the algorithm in Minecraft using ProjectRed (Integration module, specifically) and then you can easily count the gates! :-)

Have you tried telling them (1)

Anonymous Coward | about 7 months ago | (#45901161)

"We don't know."

hls design (1)

Anonymous Coward | about 7 months ago | (#45901165)

The most common languages for chip or FPGA design would be VHDL or Verilog. Now there is also High Level Synthesis (http://en.wikipedia.org/wiki/High-level_synthesis), in which you can use C/C++ directly. So if your using a tool like Xilinx's Vivado (http://www.xilinx.com/products/design-tools/vivado/integration/esl-design/) then you can go directly from C/C++ to gate count. However, even in C/C++ it probably needs lots of work from where it is.

Completely stupid question (4, Insightful)

dskoll (99328) | about 7 months ago | (#45901167)

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:Completely stupid question (1)

presidenteloco (659168) | about 7 months ago | (#45901495)

Yes, theoretically, according to Turing, you could get by with enough gates to make a couple of registers, a goto/jump instruction and a branch if is-zero test, as long as you have some read-write memory somewhere else.

Re:Completely stupid question (0)

Baloroth (2370816) | about 7 months ago | (#45901547)

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.

Not entirely true. While obviously the number of gates will depend on your exact implementation (you could theoretically use an infinite number of gates for any algorithm), there will be a certain minimum number of gates dependent on the algorithm itself. Even if you reuse gates by performing sequential algorithms, you still need to store data from previous operations and will need a certain number of gates for that.

The manufacturer is probably asking how many gates you need to implement the algorithm exactly as it is coded, with exactly as much parallel or sequential logic as it already has, and that will have a fairly specific answer. Again, you might be able to optimize the code to use fewer gates, but that would be a different question.

Re:Completely stupid question (0)

Anonymous Coward | about 7 months ago | (#45901649)

The analogy "How long is a piece of string?" is a stupid example of stupid questions. WORST ANALOGY EVER

Make life easier for everyone.... (0)

Anonymous Coward | about 7 months ago | (#45901173)

...just rewrite your software in machine code.

You need a C to VHDL translator (4, Informative)

Animats (122034) | about 7 months ago | (#45901177)

You need a C to VHDL translator. Here's a tutorial for one. [xilinx.com]

Only the parts of the algorithm that have to go really fast need to be fully translated into hardware. Control, startup, debugging, and rarely used functions can be done in some minimal CPU on or off the chip. So, for sizing purposes, extract the core part of the code that uses most of the time and work only on that.

Re:You need a C to VHDL translator (4, Informative)

Trepidity (597) | about 7 months ago | (#45901403)

One caveat to going this route: if the algorithm contains well-known operations as building blocks, you probably don't want to synthesize your own VHDL versions of those standard operations, since they already have highly optimized hardware implementations. For example, if one step of the algorithm is "compute an FFT", you probably want to use an existing FFT IP core [ipcores.com] to implements it, rather than translating some FFT C code to new VHDL.

At one extreme, where the algorithm is nothing but a chain of such cores (common in DSP applications), you could get a rough estimate just by looking up the gate counts for each operation and adding them up.

Re:You need a C to VHDL translator (1)

iggymanz (596061) | about 7 months ago | (#45901463)

I'm worried about dryriver's "electronics manufacturer", that kind of skill and knowledge should be a core competancy of any business that makes custom app chipsets

about 40 gates. (1, Interesting)

Anonymous Coward | about 7 months ago | (#45901179)

it would only make sense to reuse the same adder circuit for each addition, instead of making a separate adder circuit for each operation.
then you'd add control logic to move the data to adder circuits, multiplier circuits, etc.
then essentially what you have is a microprocessor.
then you just turn that microprocessor into the simplest one possible. which is basically a queue and a stack, and a few elementary logic operations. you can do operations a bit at a time.
so the number of logic gates your program needs it the number to make a queue and a stack, and a few elementary logic operations, and that's probably on the order of about 40 gates.

Re:about 40 gates. (1)

Behrooz Amoozad (2831361) | about 7 months ago | (#45901709)

40? How did you come up with that number?
A radio from 80s probably has more gates, and they don't add or multiply.

VHDL (3, Informative)

Anonymous Coward | about 7 months ago | (#45901181)

Implement the algorithm in VHDL and test it on an FPGA. I would imagine you'll need to pay someone $$$$$ to do that for you...

Pandas. (-1)

Anonymous Coward | about 7 months ago | (#45901189)

They are cute. I love them.

Break down your algorithm (4, Informative)

neutrino38 (1037806) | about 7 months ago | (#45901197)

Hello,

It is probable that you can break down your algorithm -(I do not mean code) into a pipeline of elementary processing and find implementations (IP) for each of them.

to give out an estimate:
- subdivise your algorithm into simpler pieces
- find for each simple piece how it can or could be implemented in hardware and the complexity of each piece.
- do the sum.

  Indeed an hardware designer or consultant would be of a great help here.

there are DSP:s on the market already (1)

zugedneb (601299) | about 7 months ago | (#45901205)

You do not have to design your own...
Your algorithm probably needs vector units, fast multiplication, wide memory bus, largeish...

I will take you and that company many years to make a good dsp, and it will not be better the the Texas Instruments ones you can buy...

Or, you can implement it in an FPGA, but a DSP with handtuned code is more energy efficient...

Here is one for vision:
http://www.ti.com/lit/wp/spry251/spry251.pdf [ti.com]

find an EE (0)

Anonymous Coward | about 7 months ago | (#45901207)

I would suggest finding someone who has a better idea of what a logic gate is. They'll know what to do.

HLS (4, Informative)

orledrat (3490981) | about 7 months ago | (#45901213)

What you want to do is called high-level synthesis (going from C to hardware description language (HDL) to generating gate-lists from that HDL) and there's plenty of software to do that with. A neat open-source package for HLS is LegUp (http://legup.eecg.utoronto.ca/), check it out to get an idea of what the process consists of.

Bluespec (0)

Anonymous Coward | about 7 months ago | (#45901219)

You could write in Bluespec then compile to SystemVerilog from there to something synthesisable...FPGA, ASIC and count transistors.

But many of those transistors will be providing necessary infrastructure in addition to the "raw" algorithm

Morons (0, Offtopic)

Anonymous Coward | about 7 months ago | (#45901221)

Only idiots write "C/C++." As soon as I see that, I stop reading. It is clear indicator that the writer doesn't know what he's talking about.

ask a stupid question: (0)

Anonymous Coward | about 7 months ago | (#45901607)

Take all permutations of inputs, generate all possible outputs, put them in a table. How much space do you need to store the table?

Well, that would give you one boundary condition, granted, a pretty extreme measure.
On the plus side, if you implement this way, it takes constant time to generate an output.

It doesn't work like that (5, Informative)

cjonslashdot (904508) | about 7 months ago | (#45901225)

It's about more than gates. It is about registers, ALUs, gates, and how they are all connected. There are many different possible architectures, so it depends on the design: some designs are faster but take more real estate. There are algorithm-to-silicon compilers (I know: I wrote one for a product company during the '80s and it is apparently still in use today) but each compiler will assume a certain architecture. I would recommend one but I have been out of that field for decades.

C code synthesis tools exist, but... (1)

Anonymous Coward | about 7 months ago | (#45901239)

There are a number of tools on the (commercial) market that can compile (a subset of) C to hardware into a hardware description language (Verilog/VHDL), e.g. from Cadence and Synopsys. See http://en.wikipedia.org/wiki/High-level_synthesis for an overview of the approach and links to tools. There are also some open source tools that can turn C code into Verilog or VHDL, but they are not very mature in my opinion.

However, you will not get a single number for gate complexity out of these tools. Depending on the requirements and tradeoffs (smaller chip area vs. higher speed, single cycle vs. pipelined implementation, target device as FPGA or ASIC), the number of gates (or logic blocks for FPGAs) required will differ significantly. From my experience, you definitely need a hardware design expert to obtain useful (i.e., more-or-less optimized) results from these tools - and you should expect having to invest significant effort for restructuring your C code so the high-level synthesis tools can grok it.

Easy calculation (5, Funny)

Anonymous Coward | about 7 months ago | (#45901241)

Here is a proven method for calculation.

If your code is:
a) C: divide the number of lines with 7
b) C++: divide the number of lines with 5
c) Ruby/Python/Java: divide the number of lines with 3
d) Perl: multiply the number of lines with 42
e) C#: resign.

It only takes one Gates (0)

Anonymous Coward | about 7 months ago | (#45901255)

...but he's pissed that the lawmakers are focused on re-election and partisan bullshit, so it'll never get done.

More details please (1)

ttg512 (221628) | about 7 months ago | (#45901261)

The answer, as you might imagine, is complicated and depends on how these gates are implemented. Think for instance you could design a chip to do this, you could write RTL to do this in an FPGA, or you could even write the algorithm into more software on an embedded processor of some kind. Is this electronics manufacturer one that makes chips or one that makes systems (boards, cases, etc). If it is the former they should have people who can work with your people to figure this out. If it is the latter then why do they care? Are they really asking you to provide a chip which implements your algorithm? Ask some more questions...

Troll bait? (1)

khb (266593) | about 7 months ago | (#45901275)

The question seems so ill-posed that one has to wonder if there's a product or service advert lurking... but assuming this is real.

Software doesn't automatically translate directly to hardware. As others have noted, break out the algorithmic core from the setup and finish. Presumably there is some part of the code which is the most critical in steady state. Describe that to their hardware engineers in whatever depth is required. Depending on the algorithm, the ASIC library elements available (or FPGA units, etc.) you may want to make some substantial adjustments to the "code" to make it fit within the design parameters of the available device. This should be an iterative process, not a single estimate based on a pure software perspective.

If there isn't a clearly identifiable set of "hot blocks" the chances of there being a good hw implementation fit is poor. If there is, it may still be necessary to change the algorithm details to fit but it should be "doable". Whether it is worthwhile depends on the volumes and the performance gains.

Use SystemC to Gate flow (0)

Anonymous Coward | about 7 months ago | (#45901285)

It's typically not that hard to convert C/C++ To SystemC and then use one of the many SystemC to gates flow. Various tools have come and gone in the past decade as C/C++ to gates flow isn't exactly optimized and is difficult to do functional equivalency checking.

Oh crap (1)

fiannaFailMan (702447) | about 7 months ago | (#45901301)

Mod this offtopic if you want but now I can't see my comments, I can't see if anyone has responded to them, and it has become almost impossible to participate in discussions as a result. WTF, /.?

Difficult, but... (1)

ciw1973 (3490985) | about 7 months ago | (#45901327)

...this should get you started:

http://en.wikipedia.org/wiki/C_to_HDL [wikipedia.org]

Find a suitable converter, then grab a free (or evaluation) version of an FPGA design tool, for example one of these (I only suggest these over the many other, probably equally as good alternatives, as I've used them myself):

http://www.xilinx.com/products/design-tools/ise-design-suite/index.htm [xilinx.com]

And with a bit of work you should be able to produce output that will essentially be your code implemented in programmable logic, and the tools will tell you the number of gates/cells required.

What I would say, is that you'll have a much easier ride if your algorithm is in C rather than C++.

Despite saying that you have no experience with this sort of thing, defining logic in something like VHDL is basically programming. Sure, you'll need to develop a fair understanding of the hardware, but with the libraries of pre-built components available from the numerous companies who produce programmable hardware like FPGAs and CPLDs, you may find you could do a lot more than you think yourself.

Re:Difficult, but... (1)

Asmodae (1155077) | about 7 months ago | (#45901667)

VHDL is basically programming

Sure, the same way software is basically just english and letters and numbers and if you understand those you can do most any software yourself! /sarc.
VHDL is code, but after cleaning up after software people who think they can write VHDL, it's not the same thing at all. The key statement is

Sure, you'll need to develop a fair understanding of the hardware

This is by no means a light or trivial task. There's even entire university degrees dedicated to it. ;) But if you have all THAT, then sure writing hardware code is a snap! In all seriousness the above statement basically says it's easy if you have the skill set already.

Just don't make the mistake of thinking that if you understand BOTH hardware and software that they are equivalent, or that everyone else shares in your expanded understanding. I've seen programs fail because people try to treat hardware like software simply because they're both captured with some text. It's a dangerous viewpoint if you want your project to succeed.

Cadence C to Silicon (1)

solidraven (1633185) | about 7 months ago | (#45901337)

Haven't tried it, but Cadence's C to Silicon might be up for the job. Also keep in mind that in hardware you have very different requirements than in software, and parallellisation has interesting effects on the number of gates. The best option is to get an EE, preferably with experience in digital design, to take a look at it. Other options are SystemC compilers, but they're not really up to production use yet as far as I know. And it is also very technology dependant, sometimes complicated logical functions that are common are implemented directly. This isn't something you can just wing!

They are the hardware people, they should know. (0)

Anonymous Coward | about 7 months ago | (#45901345)

Just give the number of gates in whatever processor you're running this thing on as an upper bound.

No good answer (1)

kosh271 (2036124) | about 7 months ago | (#45901351)

There really isn't a great way to answer your question without a detailed analysis of your code.

There are more factors to the number of gates required for a given task than just the complexity of code. Clock speed can be a major factor in determining the number of gates required for a given algorithm. Another major factor is the part you are targeting. The number of design elements in FPGAs used can change just by targeting a different device family.

Even if your algorithm was small enough to fit into a part, there are other issues that could arise (such as not enough bandwidth or pins for your memory device(s)).

It sounds like the electronics manufacturer doesn't have the resources to determine the number of gates for you. It looks like your only avenue is to ask a third party to review your code (under NDA) to help you determine the approximate gate requirements. This won't be cheap.

software as hardware?! but but but software patent (1, Insightful)

raymorris (2726007) | about 7 months ago | (#45901359)

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".

Re:software as hardware?! but but but software pat (0)

Anonymous Coward | about 7 months ago | (#45901643)

Nice troll. Algorithms can be implemented in many different ways in either software or hardware, much in the same way ideas can, because algorithms are ideas. Patents (used to) cover only specific implementations of ideas, not the ideas themselves.

Rough Approximation (1)

excelblue (739986) | about 7 months ago | (#45901367)

This is a horrible question to ask. Software is a tool to lower hardware requirements.

Compile your algorithm to the simplest RISC architecture reasonable. For most, something among the lines of ARM or MIPS works. Then, take note of all variables and add up how much RAM they'll take. Consider every bit (yes, bit, not byte) as a D-flipflop and convert every instruction (post-compile, in assembly) into a respective set of logic gates. A bit of googling should get you those values.

If your algorithm is reasonably complicated, chances are, you'll get a number that seems absurdly high compared to what state-of-art hardware is available.

In practice, it's probably best to just pick an off-the-shelf CPU and run the software on it. There might be some parts that are better done in hardware than in software, but you should get someone who knows what they're doing for that.

It's an optimization problem (5, Insightful)

swm (171547) | about 7 months ago | (#45901371)

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...

Accurate answer (3, Informative)

Sarten-X (1102295) | about 7 months ago | (#45901383)

Write out the truth table for each output as a Karnaugh map [wikipedia.org] incorporating every input. Count the number of gates needed to solve the map, and that's your answer for that output bit. Repeat for every other output bit. Add all those numbers together, and that's a fair estimate of how many gates you'll need.

Of course, this method requires that your number of input bits must be fairly small. Don't forget that memory counts as both input (when read) and output (when written). For nontrivial applications, you'll find that the number of gates quickly approaches "a lot".

Re:Accurate answer (2)

mrego (912393) | about 7 months ago | (#45901611)

Since they are translating a program/algorithm into circuitry, they need only to know the maximum number of gates that are used at any one cycle time (taking into account necessary time delays), so just adding all the gates per operation way over states the answer since and, not, or, etc. gate circuitry can be reused for different operations at another cycle time. Also, as for logic operations, run it through a Quine-McClusky optimization as well to minimize them.

Gate count more a matter of speed (2)

Yoik (955095) | about 7 months ago | (#45901409)

It doesn't take many gates for a Turing machine that will run your algorithm but it's likely to be slow. A proper hardware implementation will optimize everything and be as parallel as possible.

The problem as stated isn't adequately constrained.

"Graphics" algorithm... right (1)

ArcadeMan (2766669) | about 7 months ago | (#45901411)

You guys are probably trying to get a manufacturer to make Scrypt-mining ASICs.

Re:"Graphics" algorithm... right (1)

neiras (723124) | about 7 months ago | (#45901633)

Yep, first thing I thought too.

Not even close. (0)

Anonymous Coward | about 7 months ago | (#45901423)

You guys really need the help of a Comp E or EE. Not to be super critical but from reading your post/question it's pretty easy to see that you don't understand hardware design at all. Nothing wrong with that but you're clearly purely software. Any tools to convert code to HDL is not going to help you at this point because you're not going to understand the hows and whys of how things work on a gate level. There's no magic program that can take a program of some complexity and turn it into logic gates.

Maybe you could get by with an embedded processor and some peripheral ip blocks in your asic... maybe the whole thing is one giant 32 stage image processing pipeline. It really depends on your algorithm.

FYI reversing a bit (1 bit) takes 2 gates or 16 gates per byte. 'Add' takes several hundred if you do anything more (look ahead) then the most basic versions. 'Divide' takes thousands of gates. Any memory you use as buffers will be on chip if you want to get the performance of an asic and that costs gates (4 gates per bit) and there's no free/malloc (no memory reuse basically). Any external memory access will require a dram controller so that adds gates.

Howto (0)

Anonymous Coward | about 7 months ago | (#45901429)

1. Solicit buyers
2. Land one
3. Post on Slashdot
4. ???
5. Profit!

How fast do you need it? (0)

Anonymous Coward | about 7 months ago | (#45901435)

Speed of result and gate count are directly related to each other, except for a single bit input and output.

Multiply by magic constant, get estimate! (0)

Anonymous Coward | about 7 months ago | (#45901439)

Create some reasonable metric, for example 5 gates per instruction. Compile your program and somehow get the number of instructions in assembler, then multiply by 5 or more. In good case you could expect 1-2 gate(s) per instruction, in bad case you could expect 2-3 gates per instruction, and those two more gates are just "to make sure" you won't underestimate it.

The correct response is... (0)

Anonymous Coward | about 7 months ago | (#45901471)

If you don't have anyone on your team that has done ASICs or FPGAs, the only correct response is "We don't have the expertise here to estimate that."

People have mentioned C to VHDL translators. While they exist, they aren't magic and will not give you a useful answer. They do not "know" what parts of the design are important to do in logic and they do not "know" what tradeoffs you want in order to hit the right balance between speed, gate count, and so forth.

The key to success. (5, Insightful)

ttucker (2884057) | about 7 months ago | (#45901475)

Do not ask a computer scientist to be an electrical engineer.

Synthesis tools and estimation (1)

slew (2918) | about 7 months ago | (#45901479)

Theoretical answer:
Recode your algorithm in SystemC (a c++ library that can be used to implement a register transfer language representation of your algorithm) and synthesize it with one of the available tools (e.g., Accelera, Synopsys, Calypto, etc) targeting a typical library (e.g, 28nm TSMC), at a particular clock frequency.

Practical answer:
Ask someone with hw design experience to estimate it for you...

FWIW, nobody wants an "exact" size in logic gates, all they want an idea in complexity. The big ticket items people care about are the size in bits of RAMs (and how many simultaneous read/write ports it might need) and complicated math that is likely to take more than 1 clock cycle to complete (e.g., like a floating point math operation) and the data-width of the main data path at the throughput that you want to have. Simply multiplying the data path width by the estimated number of pipeline cycles is generally proportional to the eventual area minus the RAMS and special math ops (which is why you need to identify those parts separately).

Generally, I've found that naïve "software" algorithms have not been very amenable to HW implementation without some amount of rework and the fact that you do not have an answer to the posed question would likely lead me (and probably your potential customer), that your algorithm is half-baked from a HW implementation point of view... Just food for thought...

Write it in C (0)

Anonymous Coward | about 7 months ago | (#45901487)

Write it in C. Not C++, not Perl or PHP or, gods forbid, Java. Actual C.

Then run it through some debugging programs to get a ballpark idea of how many instructions are actually being implemented, and how many library functions are being called if you can't isolate the actual process to a small enough operation.

von neuman (0)

Anonymous Coward | about 7 months ago | (#45901489)

As far I Know, if you want to run an algorithm , you need a Von Neuman computer, with rom, ram and I/O , because your algorithm need to read and write data values and read the execution code itself. This arragement is much more eficient than singles logical gates. What You will do when find a bug in your code ? Bake another bunch of chips ?

Convert to known assemby language? (1)

Giblet535 (3480751) | about 7 months ago | (#45901499)

Short answer: you need to contract an electronics engineer. Possible: You could dump the non-optimized assemby language (-S on most compilers) for a popular processor family e.g., 80686, PA-RISC, etc. The manufacturer probably has resources to convert "this pile of 80686 instructions" to "an ASIC that does the same thing really well".

Here's my circuit for a simple problem:Good Luck! (1)

deathcloset (626704) | about 7 months ago | (#45901501)


For what it is worth, here is a circuit I developed to see what the gate configuration (nor only) would look like for the implementation of a condition that the input switches be:

0
1
01
11
http://www.neuroproductions.be/logic-lab/index.php?id=3699 [neuroproductions.be]

you know, the counting integers 0,1,2,3 - the same code that I have on my luggage. I thought there might be a fun implementation related to security or something - a hybrid mechanical/electronic locking system.

It turned out to be super hard for me to figure out this final result. Nonetheless, the result was most interesting and I encourage you to find a more efficient configuration.

I did this using basic logic and a crapton of that time-honored tradition of guessing and trial and error.

I can only begin to imagine the complexity of trying to implement and design circuits based on algorithms written in anything above assembler level.

Re:Here's my circuit for a simple problem:Good Luc (1)

deathcloset (626704) | about 7 months ago | (#45901517)

*oopsy* that should have been
0
1
10
11

but you knew that ;)

Easy... (1)

verbatim_verbose (411803) | about 7 months ago | (#45901505)

"It takes one gate that accepts our input and outputs a desirable answer. We would like you to design that gate."

Give it up... (0)

Anonymous Coward | about 7 months ago | (#45901527)

This Bitcoin mining thing will never go anywhere :-)

One MILLION gates! (1)

GodfatherofSoul (174979) | about 7 months ago | (#45901531)

Then, stick your pinky into the corner of your mouth and do your best evil laugh!

I've done this before (4, Informative)

Asmodae (1155077) | about 7 months ago | (#45901555)

There's been several people who suggested using a high-level synthesis tool to convert your software (c/c++) directly to HDL (verilog/VHDL) of some kind. This can work and I've been on this task and seen it's output before. The catch is; unless that software was expressly and purpose written to describe hardware (by someone who understands that hardware and it's limitations and how that particular converter works), it almost always makes awful and extraordinarily inefficient hardware.

Case in point - we had one algorithm developed in Simulink/Matlab that needed to end up in an FPGA. After 'pushing the button' and letting the tool generate the HDL, it consumed not just 1 but about 4 FPGAs worth of logic gates, RAMs, and registers. Needless to say the hardware platform only had one FPGA and a good portion of it was already dedicated to platform tasks so only about 20% was available for the algorithm. We got it working after basically re-implementing the algorithm with the goal of hardware in mind. The generation tool's output was 20 times worse than what was even feasible. If you're doing an ASIC you can just throw a crap-load of extra silicon at it, but that gets expensive very quickly. Plus closing timing on that will be a nightmare.

My job recently has been to go through and take algorithms written by very smart people (but oriented to software) and re-implement them so they can fit on reasonably sized FPGAs. It can be a long task sometimes and there's no push-button solution for getting something good, fast, cheap. Techies usually say you can pick two during the design process, but when converting from software to hardware you usually only get one.

Granted this all varies a lot and depends heavily on the specifics of the algorithm in question. But the most likely way to get a reasonable estimate is going to be to explain the algorithm in detail to an ASIC/FPGA engineer and let them work up a prelim architecture and estimate. The high-level synthesis push-button tools will give you a number but it probably won't be something people actually want to build/sell or buy.

profiling (0)

Anonymous Coward | about 7 months ago | (#45901603)

Everything traditional for graphics has been done for ages in software, or in traditional hardware. Algorithms are known, and have been implemented. No-one would need to ask any questions. Now there's a new kind of algorithm, and questions are being asked. Means, something unusual, used for some unusual purpose, in a context where all-purpose processing capability is too limited / too expensive / to energy-consuming. Phones have been carrying around sufficient power for quite some time, anything wired is a non-issue. Something mobile, energy inaccessible, high expected runtime. Number of gates seems to matter, a small device. Ball-pen. A dedicated silicon for this purpose, price does not seem to matter that much.Wrist-watch. The algorithm itself is unusual, else there would be no need to ask questions. Nothing really new in the 2d or 3d area. Either a different kind of 3d than what usual hardware does, voxels or similar, or rendering something holographic. Wrist watch with holographic hands?

Neat. I want one.

Please make the FPGA as big as it can fit in to keep the frequency and thus energy consumption down. Don't want to recharge my watch as often as my cellphone.

First step (0)

Anonymous Coward | about 7 months ago | (#45901609)

The first step is to compile it into an architecture-neutral assembly program. Then, appropriate tools can turn it into a machine-specific set of instructions, and the answer will become apparent, or at least a reasonable approximation!

Why not have them figure it out? (1)

Punto (100573) | about 7 months ago | (#45901615)

While an interesting question (I didn't even know hardware manufacturers were in the habit of converting software into hardware), why don't they figure it out themselves? They must have the tools/people to do it. Are you afraid they'll "steal your algorithm" if you give them the source? (that's much less interesting)

What is the architecture that will run it? (0)

Anonymous Coward | about 7 months ago | (#45901625)

Making electronics out of an algorithm depends mainly on the architecture that is going to run the algorithm. The only scenario in which estimating a gates count makes sense is if the electronic manufacturer wants to put it on an FPGA or make an ASIC out of it. If that is the case, a C-to-Gate compiler may be the route to go.

There are also plenty of off-the-self embedded processors with HW acceleration, DSP and GPU that may very well also tackle the problem efficiently on embedded software. And porting to embedded software is less expensive than converting it to gates. It depends strongly in your algorithm but the bottom line is that you may not need an electronic manufacturer as a partner.

How many gates could a gate chuck chuck if a gate (1)

Anonymous Coward | about 7 months ago | (#45901627)

How many gates could a gate chuck chuck if a gate chuck could chuck gates?

Find an engineer who is good as software/hardware (0)

Anonymous Coward | about 7 months ago | (#45901629)

and go from there. Do NOT listen to /.. HLSs have come a long way but I'd never really trust them(especially for an ASIC design). Also, FPGA LUT/BRAM/etc usage isn't really a great estimate of how many ASIC gates will be used. If you want a decent answer you're going to have to pay for it and you're NOT going to get it from /.. Good luck though, I think you'll need it.

Re: Find an engineer who is good as software/hardw (0)

Anonymous Coward | about 7 months ago | (#45901639)

At*

Matlab has a solution for this, but $$$ (1)

AmazinglySmooth (1668735) | about 7 months ago | (#45901645)

Look at Mathworks. They have a solution for this.

one approach... machine code (0)

Anonymous Coward | about 7 months ago | (#45901657)

Compile the project and take a look at the generated machine code. Take the unique set of those instructions and look at the circuits needed by your x86 architecture to execute those instructions. This could be a reasonable estimate.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>