[посоветуйте]Бакалаврская - параллельные вычисления

автоматическое (на уровне компилятора) распараллеливание «выполнения программы» в чистых функциональных языках. если не ошибаюсь, об этом много говорят, мол чистое ФП позволяет проводить такое вот автоматическое распараллеливание, но реального воплощения этого мнения вроде как нет. хотя Parallel Haskell наверное =/ но тогда вопрос: почему это не в стандарте языка? какие проблемы? каким образом можно эти проблемы устранить?

Читать об OpenMP и MPI до просветления.

Не, плиз что-то попроще. Про ФП в этом плане я знаю. Не из компиляторов.

И че?

можно посмотреть в сторону тех алгоритмов, которые реализуются в рамках MapReduce. Например, те, что перечислены в книжке Data Intensive Text Processing With MapReduce....

http://parallel.ru/research/challenges.html

Петросян.жпг

Ниче смешного эти задачи, что я привел выше по ссылке решаются у нас в рамках магистерского диссера :) Ну естественно по отдельновыбраной узкой теме.

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

ну тогда архиватор.

Интересная область - параллельное решение СЛАУ, например. Для бакалаврской будет достаточно сравнить несколько существующих подходов. Я сам хотел такое делать, даже статьи читал по теме, но научрук настоял на другой области.

Нахрен тебе практического? Короче, откапываешь что-нибудь уже готовое по вычислительной геометрии, решенное в последние лет 10-15 и пытаешься распараллелить. Например, диаграмма Вороного для отрезков. Если сильно просто, то диаграмма Вороного для отрезков в 3-ех мерном пространстве.

Пусть для начала почитает программы на http://shootout.alioth.debian.org/ для архитектур с количеством ядер > 1. Например для x8-64 и четырёх ядер там есть:

Классический пример на C++ с ручным распараллеливанием.

Пример на CL с использованием sb-thread.

На Haskell большая часть программ написанна с использованием forkIO, и ещё есть короткая программа в которой нет ни токена про параллельность, но которая паралелится именно автоматически именно компилятором.

Нужны темы работ, а не как распараллеливать. Как и так понятно.

Ну вы спросили - «что из существующих алгоритмов можно распараллелить», вот там и ответ - почти любой алгоритм при правильном подходе :) (даже нахождение простых чисел - Роб Пайк читал одну лекцию, там был пример на эту тему).

Т.е. взять любой набор интересных тем - и попробовать разделить их по критериям «можно» параллелить, или «проблематично/не знаю». С первой группой и работать.

любая задача, решаемая с помощью Генетического Алгоритма - он распараллеливается на ура

http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5...

В библиотеке SUNDIALS нет реализации векторов для OpenMP. Но есть советы, как это сделать (по аналогии с реализацией для MPI). Ну и в качестве исследовательской части можно сравнить масштабируемость задач с использованием полученной реализации.

Я заранее отвечу, что это вообще ничего не даст кроме ухудшения производительности. Применение openmp в лоб хорошо работает для таких алгоритмов, где каждый поток выполняет какую-то достаточно сложную работу. Например, очень хорошо на openmp параллелится генерация матрицы конечных элементов, ибо там надо считать интегралы.

Может быть, производительность и ухудшится - но это зависит от задач. В конце концов, реализации MPI тоже имеют определенные накладные расходы на передачу данных, тем не менее выигрыш на задачах линейной алгебры есть.

Поэтому, если система имеет достаточно большую размерность (и используются итерационные методы с заметным объемом вычислений для каждого потока), можно ожидать определенного прироста производительности и для OpenMP.

Есть конечно. Параллелятся хорошо только алгоритмы, которые входят в blas3 или используют blas3. Поэтому, если либа использует блочные алгоритмы, то сделать что-либо на openmp получится. Только зачем? Проще и гораздо эффективнее взять реализацию blas'а заточенную под свой проц и сделать в либе blas-backend.

acml и mkl, кстати, в blas3 используют openmp, но там еще идет жесточайшая оптимизация на asm'е. Я сколько не пытался так и не осилил догнать их по производительности на чистом Си. Ровно в 4 раза медленнее получается у меня dgemm, хотя я тоже делал жесточайшее задрачивание под размер кеша проца. А тупой «#pragma omp parallel for» на больших и малых размерностях не работает вообще.

Вот бакалавр прочтет это и подумает - нужно ли ему такое параллельное программирование?

Кстати, интересно (по поводу «в 4 раза медленнее») - если сравнивать результаты HPC с mkl +icc и, например, atlas+gcc, какая там ожидаемая разница в производительности?

Замятин обычно не навязывает темы. Можно с любой интерестной приходить и он будет за.

В том числе и без паралелизма.

У меня на q8400s производительность такая.
функция dgemm, размерость матрицы 4096x4096
atlas (gcc) 37gflops
acml (gcc) 35gflops
mkl (icc) 25glops

пик у процессора 42.56gflops

То что я руками писал достигало 10gflops (на 4х ядрах), при этом масштабировалось оно линейно. Никак руки не дойдут проверить на 8ми ядернике.

Спасибо, интересные данные. Рад за atlas.

меня это тоже удивило, я думал атлас сольет закрытым реализациям

Параллельные алгоритмы - имхо унылая, сто лет назад исчерпавашая себя тема. Попробуй свести к распределенному программированию. Оно где-то рядом. Зато любой нагруженный проект есть оная система. И современно, и интересно, и полезно.

Я у Замятина пишу P2P Filesystem на базе FUSE. Java+Google Protobuf. Может на Scala еще, я еще не решил окончательно

> Я у Замятина пишу P2P Filesystem на базе FUSE. Java+Google Protobuf. Может на Scala еще, я еще не решил окончательно

эээ... ты уже пишешь, но ещё не решил на чём пишешь? это как? ленивое написание?

Ну это как бы за первый месяц выбрать руководителя и тему.

Думаю магистерскую работу писать по параллельным вычислениям. Тоже над темой думаю.. Единственое, что пока в голову пришло - распознавание образов. Какие еще варианты будут?