Archives

Categories

Y
Y

On FPGA Acceleration of Bioinformatics Programs – Latency

Homolog.us blog is written by professional janitors dedicated to clean up US science. During lunch breaks and other time off from the job, we discuss bioinformatics. The name 'homolog.us' is not a spelling mistake, but is derived by taking Arabic translation of the 'O' in the original word.

Please follow us on twitter – @homolog_us.

-------------------------------------------------------------------------------------------------------------

The concept of latency is very familiar to hardware designers, but rarely to software programmers. In fact, the entire purpose of microprocessor design these days is to hide ‘latency’ from the programmers using cache and hash functions.

What is latency? It is an unavoidable component of any natural system. Suppose, you communicate to other organizations by writing letters and those letters take one day to write, one day to get processed by the person on the other side, but eight days in to-and-fro mail time. How many letters will you be able to send in a month (30 days)?

Ans – three, if the letters were all dependent on each other. You need to receive the answer of the first letter to write the second and then wait for another ~10 days to write the third.

What if the letters were mostly independent? In that case, you could potentially write 30 letters a month, which is 10x speedup compared to previous scenario. You write one letter today, write another independent one tomorrow and so on and then go back to the first one on 10th day after receiving its reply.

The above kind of delay is common to any system, be it writing letters or sending data from microprocessor to storage. However, one difficulty of accelerating ‘standard’ software programs is that their programmers never incorporate ‘latency’ in their designs. For software programmers, latency manifests into cache miss, but that component is not incorporated in the design. Often the solution appears to be buying a ‘faster’ microprocessor, i.e. one with more cache or make other efforts to fit data into cache.

For hardware designers, the solution is to untangle the ‘for’ and ‘while’ loops within critical block. That is quite a bit of work given how those programs are written.

More later…




-------------------------------------------------------------------------------------------------------------
Heroes and Heroines of New Media--2014

I am strongly influenced by Charles Hugh Smith, who runs his insightful social blog of Two Minds. I hope he will not mind, if I copy his style of acknowledgement to the supporters of our blog.

Our blog is deeply honored by the generous contribution of the following readers. Without their patronage, this site would go away.

Outstandingly Generous:  
Amemiya C. Schnable J. Bowman B.

We are also looking for subscribers to get help to finish the tutorials. Please see this post for details.

2 comments to On FPGA Acceleration of Bioinformatics Programs – Latency

  • Christopher Chang

    It’s worth noting that the points you’ve made in FPGA-referencing posts so far are fully applicable to ordinary software optimization; don’t undersell this as arcane knowledge only relevant to the most hardcore engineering projects! It takes a fair amount of scale before hardware customization is likely to be worth the effort; but awareness of rate-limiting steps and latency pays off across the entire programming spectrum–even when writing throwaway scripts.

  • samanta

    You are absolutely right Christopher and more so given that the entire world has moved to multi-threaded programming. However, when we go through the codes of popular bioinformatics program, we rarely see good hardware practices incorporated. Yet the need is there, because the users (often external) try to scale them to solve problems for large genomes.

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>