Parse data (effcienciently?) with a FPGA?

[onesixright]

Hi All,

I have zero experience with FPGA's. I watched a few YT movies (thanks Dave!) for introduction into FPGA and some LCD drivers. Thats it.

I'm questioning if its possible and if so what would be the efficiency of parsing data like json, xml with a FPGA. So in-essence the FPGA would become a h/w parser.

Would it be possible? And wood it be fast(er) then using a normal CPU approach?

Would love to to hear your thoughts!

Thanks.

[electro-logic]

You have a lot of overhead in passing data from and to CPU. It can make sense if you do also oth

[onesixright]

It can make sense if you do also oth

Sorry, oth stands for  ?

[mikeselectricstuff]

It wouldn't normally make sense to do this with an FPGA  - much easier to do on a processor.
Of course it can be done, as pretty much anything is doable on an FPGA, but the solution would end up looking pretty much like a processor, so you might as well use an existing soft core

[djacobow]

About 15 years ago when I worked for a company that designed processor-like IP with custom instructions, we had a customer who wanted to do general-purpose XML parsing in hardware. There is room for some speedup, as with custom hardware and a wide memory interface and data path you can look at, say 32 bytes of input stream at once and find token edges and their offset into the chunk in a single cycle. So that would help with the lexing step. I'm not sure what kind of speedup you'd get from that. Maybe a few times. For parsing the tokens into a tree, I can think of a few things you might do in hardware that could offer some speedup, but I think it would be hard to beat well-written code by very much.

Now, if you know you want to pull something out of some fixed structure xml or json, it's easier to imagine some simple hardware to do that. Like, if you want to go to the third element in an array, then find the hash element there named "bob" and then hash element under that named "address", one can imagine a special purpose state machine to really zip through to find the beginning of that pointer.

But then again, how fast could you possible need that?

[mikeselectricstuff]

The question is why you'd want to parse an inefficient data format that quickly, as opposed to starting with a more efficient data format, or precompiling it somewhere along the way into binary tokens .

[onesixright]

The question is why you'd want to parse an inefficient data format that quickly, as opposed to starting with a more efficient data format, or precompiling it somewhere along the way into binary tokens .

Thank you all!

@mike Your absolutely right, and it did cross my mind. TBH The XML is not important by any means.

I understand its hard to answer this if you guys don't know what is the reason/concept. My first thought would be also, your nuts. Thats what we have CPU's for!

So I'm sorry to be a bit mysterious here. Without going into the details (at this point).

I came up with a concept, that I explained to 2 people. Both where extremely enthusiastic (ofc that doesn't mean a lot).

Now I have not a clue how to move forward with this idea. I know how it should look, and I was thinking a FPGA might be a solution. It would need quiet some complex parsing of data.

The bottom line for me is: I don't want to go in the area of SoC and creating h/w that would basically run something like linux. If possible i would like to avoid that (for specific reasons).
I dont want boost my idea by any means, it might be a sh!t idea and undoable. For sure it has some drawback (i can name a few), but could be amazing start of something new.

I would actually prefer to open-source it, but not a clue how to approach it. Guessing it would be a pity if this would be commercially exploited, worse being patented (maybe it is, didn't check it).

Is there a EEVBLOG Think Tank, where this stuff can be discussed without getting into NDA's BS :-) ?

Any thoughs  ?

[mikeselectricstuff]

The question is why you'd want to parse an inefficient data format that quickly, as opposed to starting with a more efficient data format, or precompiling it somewhere along the way into binary tokens .

Thank you all!

@mike Your absolutely right, and it did cross my mind. TBH The XML is not important by any means.

I understand its hard to answer this if you guys don't know what is the reason/concept. My first thought would be also, your nuts. Thats what we have CPU's for!

So I'm sorry to be a bit mysterious here. Without going into the details (at this point).

I came up with a concept, that I explained to 2 people. Both where extremely enthusiastic (ofc that doesn't mean a lot).

Now I have not a clue how to move forward with this idea. I know how it should look, and I was thinking a FPGA might be a solution. It would need quiet some complex parsing of data.

The bottom line for me is: I don't want to go in the area of SoC and creating h/w that would basically run something like linux. If possible i would like to avoid that (for specific reasons).
I dont want boost my idea by any means, it might be a sh!t idea and undoable. For sure it has some drawback (i can name a few), but could be amazing start of something new.

I would actually prefer to open-source it, but not a clue how to approach it. Guessing it would be a pity if this would be commercially exploited, worse being patented (maybe it is, didn't check it).

Is there a EEVBLOG Think Tank, where this stuff can be discussed without getting into NDA's BS :-) ?

Any thoughs  ?

For pretty much anything, you'd only go to an FPGA if it's not practical on a processor, so start there

[obiwanjacobi]

As I understand it, FPGA's shine in (massive) parallelism. Parsing any stream of bytes is sequential by nature. Indeed try a CPU/DSP first. Dedicated hardware is always faster than programmable hardware (FPGA). So if speed is a thing, try to fit existing chips. Softcores (CPU logic in an FPGA) are fun and sometimes a good choice - but not fast.

[2c]

[mikeselectricstuff]

The other question is where is  this data coming from ? - can it even arrive fast eough to need FPGA-level speeds ?
 

[NorthGuy]

If you want to parse millions of files, you can do parallel processing by distributing the files between many CPUs.

[andersm]

If you figure out where the parsing bottlenecks are, you could potentially extend a soft core with special instructions or accelerator peripherals. However, you have to define your goals and metrics carefully. If you want to do better than a modern CPU with a SIMD-optimized string library, you have to define what "better" means. And as Mike posted, you have to think about what produces and consumes the data. An "XML-parsing FPGA" isn't very useful by itself.

[amspire]

You could stream data through a FPGA and make simple changes to speed up processing - deleting extra blank spaces, substituting characters - I really do not know what sort of JSON files you are using.

However, as others have said this is a job suited to a processor, and as your first FPGA attempt, you are probably starting in second or third year University level. The trouble with doing something very complex in a FPGA is no-one else will understand your logic, and after 6 months, you will not understand your own logic either.

The best starting FPGA projects will be simple to understand logic, counter, data buffer. etc tasks. If you can show a block diagram to someone and they understand exactly what the FPGA is doing, that is a good start.

If you try and draw a block diagram explaining your json parsing and explain what the json gets converted into, it will probably be a nightmare of a block diagram.

It is initially very difficult to understand the difference between computer procedural code and FPGA logic state code and starting with json parsing that is probably a procedural task will make life impossible as a FPGA newbe. A FPGA does not step through instructions. The thing that makes a FPGA powerful is you can have 100 different logic circuits and all of them function at full speed at the same time - all in parallel. Micrcontrollers cannot do that.

[onesixright]

All thanks for the feedback, i'll take it to heart ! 

Let me lift a tip of the iceberg.

I came to the FPGA solution since I need to drive a high-res TFT/LCD, based on a data stream. Now that (data) could be some propriety format optimised for the FPGA or I thought of sending some standard format like XML, JSON, etc. XML is not written in stone. I was just interested if you could by-pass the whole CPU and implement this on FPGA level. But thats a bridge to far.

In conclusion: Its now clear (to me) that the FPGA is not sensible solution, possible: yes, but extremely complex (and not important hard to maintain).

Thanks again!

[hans]

The problem with most FPGA solutions come when you need to implement an algorithm that has loops with data dependencies in them.

In many cases we use loops in software as a short hand notation, e.g. if you have a FIR filter. In that case a simple loop can multiply input data and a filter coefficient, and add the result to an accumulate register. A typical implementation on a computer may do this by calculating intermediate sums 1 by 1, thus expanding the loop in time.

If you want to synthesize a fixed-width FIR filter, you can essentially write the same code in VHDL. However, if you were to write such a for loop straight away in a process, it would instantiate an multiplier and adder for each single tap, thus expanding the loop in space.
Of course you can also create a description that expands in time, but you would need to describe what happens across the multiple cycles with some extra registers/state.

This makes FPGA's very unattractive for parsing XML or JSON protocols, as there are many loops in such a system, often requiring intermediate results from other loops. In addition one cannot use recursion, so alternative implementations often then require more loops.
You would either expand massively into space or need to keep track of every single state that needs to be carried over from clock cycle to clock cycle.

For sure anything is possible, if it sufficiently constrained to not expand into infinite hardware. Additionally I doubt it would be much fun writing such a thing in a language as VHDL. I would consider writing such a system in a higher level language like Clash, as it's very similar to functional programming. However even in that case it would be no trivial task.

[nctnico]

I came to the FPGA solution since I need to drive a high-res TFT/LCD, based on a data stream. Now that (data) could be some propriety format optimised for the FPGA or I thought of sending some standard format like XML, JSON, etc. XML is not written in stone. I was just interested if you could by-pass the whole CPU and implement this on FPGA level. But thats a bridge to far.

You could do this with a combination of an FPGA and a soft-core. Parsing the XML, JSON, whatever can be done by the softcore and the display driving can be done by the FPGA. One step back is to use a microcontroller which can drive a TFT screen. Another solution is to use a SoC and don't go beyond the bootloader. Modern bootloaders like u-boot have so much drivers and connectivity built in that they have morphed into a mini OS themselves which you can use for a bare-metal like solution.

[electro-logic]

*other things

It can make sense if you do also oth

Sorry, oth stands for  ?

[John Coloccia]

Just as a general principal, the first step when discussing if you can do something "fast" is to ask "how fast?" Once you define the problem scope, then you can pick the simplest technology that gets you where you want to go.

[hamster_nz]

A lot of FPGA protocol stacks are in essence parsers - video, audio, network routing and so on.

As long as you can avoid recursion and deeply nested structures you can pretty much build an FSM.to process most things.

[daybyter]

FIX protocol parsing is essential, if you want to do high performance trading. FPGAs are used for this.

[NorthGuy]

FIX protocol parsing is essential, if you want to do high performance trading. FPGAs are used for this.

You get front-run by market makers no matter what speed. I don't think FPGAs can help with that.

[hans]

Incorrect. FPGA's are use plenty in high-speed stock trading. These guys play "the game" borderline cheating.

I've been told the story that these guys were keeping lots of TCP connections indefinitely  open that are used to set up transactions. What they did is split up the packet to be sent for a transaction and sent a part of them. E.g. header and footer are already sent, it just "so happens" that the middle payload packet must have been dropped somewhere (how inconvenient..) that contained pricing and quantity information.
Then when it is time to buy, they fill in the remainder of their "TCP cheque" and get the transaction done with only 1 packet latency.
They have told this because this trick has been disallowed on most exchanges.

This same company told they are increasingly offloading their algorithms to FPGA's. But of course not what, as I bet that's stored in a big safe at their company.

[nctnico]

Incorrect. FPGA's are use plenty in high-speed stock trading. These guys play "the game" borderline cheating.

I've been told the story that these guys were keeping lots of TCP connections indefinitely  open that are used to set up transactions. What they did is split up the packet to be sent for a transaction and sent a part of them. E.g. header and footer are already sent, it just "so happens" that the middle payload packet must have been dropped somewhere (how inconvenient..) that contained pricing and quantity information.
Then when it is time to buy, they fill in the remainder of their "TCP cheque" and get the transaction done with only 1 packet latency.
They have told this because this trick has been disallowed on most exchanges.

This same company told they are increasingly offloading their algorithms to FPGA's. But of course not what, as I bet that's stored in a big safe at their company.

That doesn't surprise me at all. Source: a couple of years ago I was offered a well paid job as an FPGA deverloper at a company which made these kind of fast trading systems. Low latency is extremely important for these guys and they all want the latest and greatest.

[Berni]

Now that's a nice trick of TCPIP.

With all of this i think it would make more sense to have the stock market run on a 1 second tick so that people wouldn't be trying to outrace each other with there trading bots. Put in your trade decision for that second and when the second is over the stock exchange returns the results of that.

[NorthGuy]

Incorrect. FPGA's are use plenty in high-speed stock trading. These guys play "the game" borderline cheating.

I don't think high speed trading is cheating, and of course they try to be as fast as they can. However, there's the next level where the cheating takes place. These guys see your orders before it hits the floor no matter how fast you are. You can see a bid sitting there for long time, but just the moment you decide to take it, the bid magically disappears in a matter of milliseconds. This could not have happened if they didn't see my order coming. I haven't traded for a long time, but I doubt it is now any different than it was back then.

[daybyter]

https://www.euromoney.com/article/b12xygfs5959wx/fx-how-low-can-you-go-new-solution-cuts-tick-to-trade-latency-to-120ns

I'm actually working on verilog code for FIX parsing to generating. Would love to test one of these:

https://netfpga.org/site/#/systems/1netfpga-sume/details/

or these:

https://www.bittware.com/fpga/servers-systems/terabox/

 

[hans]

Incorrect. FPGA's are use plenty in high-speed stock trading. These guys play "the game" borderline cheating.

I don't think high speed trading is cheating, and of course they try to be as fast as they can. However, there's the next level where the cheating takes place. These guys see your orders before it hits the floor no matter how fast you are. You can see a bid sitting there for long time, but just the moment you decide to take it, the bid magically disappears in a matter of milliseconds. This could not have happened if they didn't see my order coming. I haven't traded for a long time, but I doubt it is now any different than it was back then.

I am not saying they are cheating (that is defined after all by the market who makes the technical rules), what I wanted to illustrate with that phrase and the TCP story is they will do whatever it takes to get the lowest latency over their competitors. They are competing at microsecond levels of latency. This where their bread is earned, aside from good trading algorithms of course.
This is perhaps one of the weird cases where speed is king above anything, even if it is at the cost of maintainability and readability of the code. They try to maintain a high quality through rigorous testing procedures and code reviews, while staying "agile" enough that they have a short deployment path to production.

I certainly do believe that their network connection for their trading box more or less runs straight into a FPGA. If you're not in the same building to trade or use a crap network stack, you've already lost so to speak. This is where FPGA's can offer high levels of granularity and parallelism that is very valuable.

[NorthGuy]

120 ns doesn't sound realistic. During this time, the signal can only travel 60 feet (assuming wires, not silicon) - you need to be very close. How many high speed traders can you possibly fit into such small space?

Would love to test one of these:

https://netfpga.org/site/#/systems/1netfpga-sume/details/

Just press the button:

https://store.digilentinc.com/netfpga-sume-virtex-7-fpga-development-board/

[daybyter]

As I understand, the 120ns are the time from getting into the trader's PC to the moment, when the PC sends the order. The signal remains in the fpga network card, so it doesn't have to travel very far. And there is no real trade logic involved. So no calculations, if the trade would be profitable.

I would buy the sume card in a second, if it was just a bit cheaper... ok...a lot cheaper...

[nctnico]

120 ns doesn't sound realistic. During this time, the signal can only travel 60 feet (assuming wires, not silicon) - you need to be very close. How many high speed traders can you possibly fit into such small space?

The trade orders are being timestamped as well so they don't need to be handled realtime.

[hamster_nz]

As I understand, the 120ns are the time from getting into the trader's PC to the moment, when the PC sends the order. The signal remains in the fpga network card, so it doesn't have to travel very far. And there is no real trade logic involved. So no calculations, if the trade would be profitable.

I would buy the sume card in a second, if it was just a bit cheaper... ok...a lot cheaper...

Have a look at some of the http://www.metamako.com hardware.... Still not cheap :-)

[daybyter]

I guess I have to continue playing with my de0 nano for a while...
;(

[NorthGuy]

The trade orders are being timestamped as well so they don't need to be handled realtime.

They don't handle orders. They place them. Say, they somehow detect that a big buyer wants to buy lots of Microsoft stock. So they quickly place bunch of orders to buy Microsoft, the price goes higher and then they sell their Microsoft to the big buyer at this higher price - the whole thing takes few seconds to accomplish. The big buyers can do very little to defend against this. But, if other fast trade guys detect it earlier than you do, they get cheap Microsoft and, in the best case, you're left with nothing, or the price may go too high, the big buyer may back off and there's no one to buy your Microsoft from you, so you're holding the bag.

[Marco]

HFT has also turned stop loss into even more of a mug's game.