“Accelerate 2012 parallel programming contest” or “6 ultrabooks and 10 SSDs are enough for everyone!”

Hello!
Last week on Habré was marked by a series of hacker posts - both VoIP and online traffic jams were hacked .
I propose to continue the week more constructively - to solve the global problem of genetics in parallel programming.
To do in the past month should be nothing at all: find in two lines consisting of nucleotide symbols A, T, G and C, the longest common substring .
The prizes have grown and strengthened compared to the previous time - today there are 6 Asus Zenbook UX31E ultrabooks and 10 SSD drives with a total capacity of 800 gigs at stake .
Is it tempting?

What are you talking about?

You have been given a reference string (for example, this one:) GATGAGCATGTGTTGAATCCTCAand many long input strings (here is one of them:) GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT. It is necessary for each pair of reference and input strings to find the longest common substrings and return their "coordinates". In the example, the answer is (5 13 15 23)and (5 13 44 52), that is, two substrings are found:

#код на Питоне, строки в ответе должны нумероваться от единицы, поэтому '-1'
ref = 'GATGAGCATGTGTTGAATCCTCA'
input = 'GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT'
ref[(5 - 1):13] == input[(15 - 1):23] #True
ref[(5 - 1):13] == input[(44 - 1):52] #True

At your disposal there is a reference code that correctly, but very slowly solves this problem with brute force.
Does that sound simple?

How to decide?

Here the fun begins. I will offer several options that may be useful:

• The easiest way: parallelize reference code by data, for example, using OpenMP and dividing the work on input tests between threads. But you can share the work in different ways. Only input strings? Fragments of the reference string? It greatly depends on their size and quantity - you decide.
• A more interesting way: take the reference code, run it through Intel VTune Amplifier XE and parallelize the algorithm itself intelligently
• A smarter approach: take one of more than 9000 substring search algorithms in a string and try to find the best one for this task
• The most advanced approach: combine the previous paragraphs, taking a smart algorithm and parallelize it according to instructions and data

What to choose? I want a hint!

What you can choose, we can’t advise. Someone likes to write on pthreads, someone on OpenMP, and someone likes to use parallel functions from TBB and maybe even MKL.
One thing is certain - very smart ideas and thoughts are often discussed on our forum . For example, it's worth looking at the instructions in SSE4.2.

What can I write on?

Unfortunately, our automated testing system is too young to support all programming languages.
This time we taught her to understand C ++ (despite my sincere love for python and Java Script), so I will have to write in the good old C ++.
The development platform can be any, but the code will be collected and tested on a Linux machine (Debian stable - kernel 2.6.32) with gcc installed (version 4.6.2 for pthreads lovers) and Intel Parallel Studio XE 2011 (for those who choose Intel Compiler, optimizing the code for our processors).

What about the prizes? I want an ultrabook!

The first three teams that wrote the fastest code and sent the solution before May 16, we will give Asus Zenbook UX31E per participant.
The second three teams - on the SSD 320 Series 80Gb .
The 4 more participants who write us the most interesting Intel Software Network blog posts will also get SSDs.

So, once again: one task , one month, 6 ultrabooks and 10 SSDs for the best participants from Russia and the CIS. Good luck to

everyone who decides to participate !

The organizers and judges of the contest are ready to answer any of your questions in the comments.