BabeufИз вашего описания, алгоритм совершенно не понятен. А из-того что понял могу предположить, что задачу можно оптимизировать алгоритмически.
Вопрос: Можно ли в такой ситуации использовать параллельные вычисления, и если да то как?
Да. Если алгоритм вычислим, то он должен быть вычислим на машине Тьюренга. А это не что иное как машина состояний, а распараллелить можно любую машину состояний. Правда не всякий алгоритм распараллеливание будет выполняться быстрее прямого. В вашем случае очевидно, что будет ускорение в разы.
Существует несколько технологий несколько технологий для распараллеливания.
1. Использовать готовые библиотеки: FFTW, cuFFT, cuBLAS-XT и тд.
2. Писать на специальном языке: CUDA, OpenCL, OpenMP (расширение Си/Си++ и ряда других), intrinsic (расширение си/си++) и тд.
3. Использовать средства языка и ОС: к примеру в юниксе fork, или кросс платформенное boost.thead и тд.
На самом деле в 3 пункте я имею в виду делать распараллеливание собственноручно, своими мозгами.
Может можно почитать как организуют параллельные расчёты при работе с массивами?
Да тут всё просто и очевидно. Можно и без книг. Циклы не зависимы по данным поэтому можно просто запустить параллельную обработку каждого витка цикла в своём потоке.
Затрудняюсь дать ответ. Дело в том что на данный момент общей методике нет. Да и в книгах даётся упор обычно на какую-то конкретную технологию, а не на все сразу. Да и стоит сказать, что параллелизм ещё имеет классификацию по данным и по командам, а по этому подходы к распараллеливанию несколько отличаются.
1)
http://www.intuit.ru/studies/courses/586/442/infoВидео курс: основы распараллеливания программ