Take the 2-minute tour ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.

I have 1500 lines of 16-bit data that need processing. I designed a microcontroller to execute some data processing algorithm on the dataset. It does well when the number of lines is small (< 100), but quickly explodes as it increases.

How do you normally deal with large amount of data while maintaining a small area? Bear in mind I have limited experience in FPGA implementation in general.

share|improve this question
    
I think you need to give us some idea of the "processing" you are doing. Is it maths (real, or fixed point)? Sorting? Other kinds of selections? Table look ups? –  Martin Thompson Jun 26 at 11:04
    
Well, it's a complicated algorithm involving 400 lines of MATLAB code. Basically it takes accelerometer data from a wrist-worn sensor and classifies movements into different elementary categories (fetching, pouring, drinking, etc.) –  geft Jun 26 at 11:06
    
(At the risk of not fully understanding your use-case) some initial thoughts: a) consider a data-reduction approach such as Eamonn Keogh's SAX which can handle data in a stream b) use external RAM connected to the MCU via SPI/I2C to expand storage (like @tjester) and c) I don't get your comment below ("RAM only allows 2 elements at once") since things like C (a common MCU coding platform) supports arrays as does Matlab (C uses 0-indexed arrays). –  PlaysDice Jun 26 at 13:17
    
@PlaysDice The RAM IP used in Altera only allows up to 2 simultaneous accesses, so I built an array. However, that array synthesizes into an enormous amount of logic elements. Currently I'm trying to modify the code such that only 2 accesses are required. I think it should reduce the size considerably at the expense of much slower speed. –  geft Jun 26 at 13:20

2 Answers 2

up vote 12 down vote accepted

I'm assuming that you are performing a data processing operation on 1500 16 bit words.

In general FPGAs allow the trade off of reduced area for decreased speed and increased complexity.

Let's say your algorithm was autocorrelation which is something that has n2 complexity, and would fly at 100 elements but take forever at 1500 elements (225 times longer).

In an FPGA you could design a small module that would hold a sample counter, an offset counter, and an accumulator. The sample counter would go up once per every few clock cycles, the offset counter would go up once per loop of the sample counter. The sample counter would be one address into the data, and the offset + sample counter would be the other address. The product of the two would be added into the accumulator. At the end of the sample counter loop, the result would be written into the output data buffer, and the accumulator cleared.

This is probably the minimum area implementation. If it's fast enough, great, but if not you have flexibility that you did not have in the microcontroller. You can pipeline the design to make sure that you get one multiply accumulate per clock. You can make sure you are using block rams and hard multipliers for fastest Fclk from the synthesizer/place-and-route tools. Finally, you can increase parallelism, at the cost of area. You could add an additional multiplier to perform more than one operation at a time. This will double throughput, but also double memory bandwidth.

This is all much much harder than writing microcontroller code, but you have so many degrees of freedom, that you can converge on an optimal solution.

share|improve this answer
    
What is the terminology for that kind of design? I don't think you are talking about general-purpose microprocessors. –  geft Jun 26 at 13:23

Generally speaking the way FPGAs are designed if your data were stored in a RAM style memory and the processing done with a simple micro controller the only increase in processor size you should see should be your addressing width and related signals/modules (IE cache).

Controllers are generally designed to scale nicely with increasing memory spaces, after all, your intel processor might use 4, 8 or 16 GB of memory with the same architecture, so they are related but only as follows: To individually access 1500 elements requires log2(1500) =11 bits of addressing, 100 lines (7 bits). That said, the number of required bits less than doubles so this does not account for the described “explosion” so the problem likely lies in how the data was stored (IE non RAM like parrallel access / coding accident) - so on to methodology.

Two general ideas:

1) That FPGA are a generalist jack of all trades and not optimal in storing large data (the way DRAM is at least).

2) That coding RTL for FPGA is not like writing software for processors. You write RTL to utilize the FPGA features and shape those into the patterns you require (if possible), unfortunately what often happens is that if you write RTL that does not nicely map to the functionality of the FPGA nicely so the software will "help" you and find a way to do what you asked, or try and fail, and then often fail to communicate the nature of the result in a humanly comprehensible fashion. The software is always interpreting what you actually want, so you need to always be checking that those guesses were accurate (reading tool logs and reports).

It is very helpful if you can draw or conceptualize somehow your design in gates or preferably luts and flip flops. If you can do that you can probably get a rough idea how many resources you might expect it to use. If you can visualize the hardware and understand how your language (Verilog or VHDL) defines that hardware then you are more likely to write code that the tools will interpret correctly (But go through the resource reports like a hawk anyway). Obviously Rome was not built in a day and this takes practice.

So in line with the philosophy of "utilizing the hardware that exists" consider how your 1500 lines are stored in the FPGA. If they are stored as bits in 1500*(data width) flip flops you are going to burn through your resources.

the efficent memories in FPGAs have a rigid structure and this means that your controller might have a 1500 word memory space but that should only be accessible 1 address (sometimes 2 addresses) in a memory at a time because that is one of the ways you can efficiently implement it. When you constrain the problem this way the FPGA can, often with tool help (IE ip catalog, others), impliment an efficient memory (example BRAM). For larger data sets people generally use actual memories that are outside the FPGA on their board when necessary and practical. This may not be the access pattern you desire but it is what generally scales for many cases. If you are for example trying to design a different access style for you data, example a CAM (content accessable memory) doing so on any platform is very expensive in terms of luts and gates relativly speaking.

share|improve this answer
    
The problem is that my design needs access to multiple data simultaneously. Using a RAM only allows up to two elements at once. I guess I'd have to redesign the whole thing. –  geft Jun 26 at 9:20
    
FPGAs have many small independent block RAMs (size in the order of 8kbit) that can be accessed in parallel. It could be a huge performance gain if you manage to fit your data processing design around that. You could store the same data in multiple RAM blocks just for the parallel read access, for example. –  maxy Jun 28 at 12:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.