1

I am a programmer new to electronics. I wanted to get a perspective on wether Programmable logic is feasible in allowing a basic math algorithm to be accelerated.

Wanting to solve a ray-intersection algorithm (few multiplications and subtractions ) over a grid of 800x600 (480000) numbers. [I understand that integers would be ideal, and control logic is frowned upon - these constraints I can work around]

Everything I have researched so far says that I can offload this processing from a processor onto a FPGA could be programmed that would calculate the problem space in a very efficient manner.

few questions:

I am thinking of using a CPLD - perhaps literally an Altera MAX® 10 - does this provide the right scale device to get this type of problem set complete ?

If I wanted to calculate the problem set 100/sec would that be possible?

(assuming performance is a problem) Can the problem be easily divided amongst different chips - where each chip wrote it's solution to a different region of ram?

Is this sort of project feasible to attach to a lightning bold/ usb3 / sata or pci express slot in a PC ? - what type of investment does it take to create a board that sophisticated (timing-wise)?

Could this be done with DSP chips? (I'm having a hard time understanding where DSPs are no longer useable - I understand there typical use in filters etc ... but how much more applicable can they be ? Can they perform simple integer math operations?)

Could this be done with discreet logic chips? - I was looking at a this EE project http://www.ele.uri.edu/~vijay/ProjectELE447.pdf ... which described all manner of ALU and multiplier chips - could these simply be piped together to express this algorithm efficiently?

How would my needs change if I needed to solve a grid of 4000 x 2000?

Thanks for your time

triple
  • 11
  • 2
  • 1
    You do realize that your algorithm uses floating numbers? Do you realize that CPLD cannot perform even such thing as multiplication, not even in integer form? – Ale..chenski Nov 01 '16 at 22:09
  • 1
    Have you considered using a GPU for this? It'll be much cheaper and faster for almost all floating point workloads. External hardware is only worth it if you have very tight latency requirements. – pjc50 Nov 01 '16 at 22:18
  • @AliChen I would'nt mind utilizing the algo in integers - if CPLD's are not addiqute - what level FPGA would be? – triple Nov 01 '16 at 22:20
  • @pjc50 yes this is perfect for GPU's - but I am also wanting to understand the performance comparison between PL and GPU's and also evaluating using this in low power - embedded environment – triple Nov 01 '16 at 22:23
  • If you just want to solve the problem for a specific data set and the time it takes to solve the problem, then use hardware that's already built like a GPU. If you need portability or you have a real time constraint (you need to solve the problem in x msec) then look at DSP's and FPGA's. Use a PC and throw more hardware at it so you don't have to waste time programming. If you need an FPGA, simulate it and see what your hardware constraints might be, then pick an FPGA. If you haven't used an HDL I wouldn't recommend it as you don't want to be dev and learning at the same time. – Voltage Spike Nov 01 '16 at 22:40
  • How much experience do you have with FPGAs? What you are undertaking is not a simple task, and depending on the complexity of the algorithm it could require a great many DSP block resources to calculate at the speeds you are thinking. Your best bet would be to break the design down into how many multipliers/adders that you would need for the required number of grid elements and then how many of those could be shared while still achieving the required speed - if you did one element at a time, you would only need one calculation block, but for multiple in parallel you need more. – Tom Carpenter Nov 01 '16 at 22:42

1 Answers1

2

This is, presumably, for ray tracing acceleration?

See also Can FPGA out perform a multi-core PC?

A colleague of mine benchmarked this and came to the conclusion that FPGAs would outperform a PC once you had more than about 100 independent, integer tasks that would fit in the FPGA. For floating point tasks GPGPU beat FPGA throughout. For narrow multithreading or SIMD operation then CPUs are extremely optimised and run at a higher clock speed than FPGAs typically achieve.

The MAX10 is a range of FPGAs of varying sizes. They certainly are capable of multiplication: up to 144 different 18x18 calculations per cycle. You need to be careful with FPGA designs not to end up limited by the speed of your DRAM. It's also a fairly substantial project to learn to program one from scratch and the tools are kind of frustrating.

Can the problem be easily divided amongst different chips - well, probably, this kind of tile-based solution is not unusual. Partitioning it is for you to work out or a software question. Remember that coordination between devices is much slower than within devices.

PCIe: I was involved in a project that built some multichannel fast ADC boards with FPGAs mounted in PCIe cards. We had half a dozen soldered by hand by experts, resulting in them costing about $1000 each. The layout took a few weeks; it was done by a graduate student with an experienced engineer looking over his shoulder regularly.

DSPs are built to do integer maths, especially multiply-accumulate (a=b*c+d). See What is the difference between a DSP and a standard microcontroller? They're generally offering similar functionality to SIMD instructions; Intel offer a multiply-accumulate since Haswell.

Could this be done with discrete logic chips?

The paper you linked looks like someone's thesis project of doing actual silicon design - taking that out of the simulator and building a chip from it is again a multiple-thousand dollar operation, and very rarely worth it.

The other approach of assembling chips of varying functions on a PCB has not been sensibly fast since the early 80s.

Community
  • 1
pjc50
  • 46,540
  • 4
  • 64
  • 126
  • First, thanks a mill for actually thinking about my problem - very thoughtful answer. **> This is, presumably, for ray tracing acceleration?** correct :) | **> a fairly substantial project to learn to program one from scratch** totally agree, I would love to hire someone with real experience to make this happen - is this a freelance-able project? **> PCIE:dozen soldered by hand by experts, resulting in them costing about $1000 each.** Hmmmm, is this meaning that interfacing with PCIe is expensive - or was there some other reason these chips needed to be soldered by hand? – triple Nov 05 '16 at 01:20
  • I was trying to convey that while it is *possible* to assemble the big BGA chips by hand, it's not easy. Whereas the fully automated lines are unsuitable for short runs. I still don't know whether this is a commercial project or a hobby project of yours; I could reccomend my former employer who have the "real experience to make this happen", but they are not cheap. If it's commercial, you need to ask yourself why you're doing this and NVIDIA aren't. – pjc50 Nov 05 '16 at 10:38
  • .. or e.g. https://imgtec.com/blog/powervr-gr6500-ray-tracing/ ; if it's a commercial project, patent clearance may be a problem. – pjc50 Nov 05 '16 at 10:39