Один из алгоритмов, который предлагается распараллелить - это генетический алгоритм, с помощью которого ищутся траектории (пути) движения редундантного манипулятора в пространстве с препятствиями. Ожидается, что в результате распараллеливания он будет работать быстрее и быстрее находить нужные пути.

Генетические алгоритмы не всегда можно эффективно распараллелить. я бы даже сказал, что распараллеливание не самый эффективный способ оптимизации ГА по скорости. Тем не менее... 
Сколько алгоритм сейчас работает по времени на вашей машине? Какое время вы бы хотели получить? Сколько, в относительных единицах (%), времени тратится на данный алгоритм в рамках программы целиком?
Что представляет собой ваша функция цели?

Что касается времени работы алгоритма, то она зависит от сложности пространства препятствий. Чем сложнее пространство с препятствиями, тем больше будет работать ГА, ищущий пути для редундантного манипулятора. Следовательно, если распараллеливание даст нужный эффект, то с его помощью можно будет в приемлимое время прокладывать траектории путей манипулятора в более сложном пространстве.
Функция цели определяется следующими параметрами:
1) Пригодность по достижению цели;
2) Пригодность по достаточности длины манипулятора;
3) Пригодность по укладываемости  и достаточности звеньев манипулятора;
4) Пригодность по допустимости углов поворота;
5) Пригодность по пересечению с препятствиями;
6) Пригодность по толщине манипулятора.


Это сообщение отредактировал(а) Rasool - 26.9.2011, 12:41

Rasool, случаем это не похоже на обход дерева снизу вверх? Если похоже, то довольно легко параллелится (n потоков, каждый берет из очереди ветку маршрута и проверяет ее до разветвления, все разветвления добавляет в очередь).

Да, есть алгоритм метода ветвей и границ, который ищет пути для редундантного манипулятора, который тоже можно успешно распараллелить.
Мне сейчас нужно определиться в "железе" - на чем лучше делать: на настольной многоядерной системе или же арендуя облачный кластер.

Rasool, для дисертации, думаю, достаточно и настольного компьютера. А кластер уже лучше использовать для решения практических задач.

Достаточно для тестирования, но к сожалению не всегда.


Надо определиться не в железе, а в целесообразности распараллеливания в системе с общей памятью (многоядерные процессоры), в системах с распределенной памятью (кластера) или на GPU. (Комбинации также возможны).
Так как методы распараллеливания могут кардинально отличаться в зависимости от архитектуры планируемой системы.

Если к вопросу подходить с наивной точки зрения, то после портирования задачи, которая успешно масштабиравалась на SMP, на суперкомпьютер, можно и уменьшение производительности получить раз так в 100 (например, забыв что резко подорожали синхронизации и обмены данными).