Распараллеливание метода Гаусса-Зейделя.

Почитай про fork-join. Даже если в твоей версии жавы его нет, можно сделать что-то похожее на executors

Если код писался без расчета на параллельность, то распараллелить не получится, придется переписывать с нуля. А что за материалы ты нашел? Слова «блочный алгоритм» там есть?

При написании оригинала о параллельности никто и не задумывался. Варианта переписать с нуля нет из-за нехватки времени. Сейчас думаю просто взять имеющиеся методы и запустить их параллельно на разные куски данных + добавить синхронизацию. Главная проблема пока что с передачей параметров в нити, пока кроме костылей с глобальными переменными ничего не придумал.

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

А какая размерность у задачи?

2

А целевой размер сетки и на сколько потоков параллелить?

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

Варианта переписать с нуля нет из-за нехватки времени. Сейчас думаю просто взять имеющиеся методы и запустить их параллельно на разные куски данных + добавить синхронизацию.

И почти наверняка получите проигрыш в производительности из-за чутьли не глобальных блокировок.

Главная проблема пока что с передачей параметров в нити, пока кроме костылей с глобальными переменными ничего не придумал.

Работа бъется на этапы:

1) пишется тесты имеющегося алгоритма.

2) алгоритм рефакторится в функциональный стиль - немутабельные объекты и набор статических методов без состояний. Никаких глобальных переменных все данные через параметры методов - результаты через return или коллбаки.

3) тестируется

4) разделение данных и перенос «тяжелых» частей на пул потоков.

5) тестирование

ps. алгоритм не смотрел, так как если у вас есть реализация и вы на нее молитесь, то надо на нее смотреть, а мой список - просто универсальный план работы.

Размер сетки и количество потоков сейчас не сильно важны, главное сделать параллельное выполнение. Отладка идёт на сетке в 20к и в макс. 12 потоков.

Проигрыш в производительности допустим на данном этапе.

По этапам всё понятно. Но вопрос у меня в том числе и в способе передачи переменных тредам ибо стандартные методы жабы этой магии не обучены.

Да как Вам сказать.... не знаю как на яве, а на нормальных для числодробилок ЯП часто бывает что распараллеливание дает не ускорение, а замедление. Т.е. должны быть веские причины, что бы так вот взять тупо и кинутся параллелить.

Похоже тут надо начинать с изучения явы.

Параллелить возникает желание, когда видишь, что одно ядро завалено на 100%, а остальные 11 прохлаждаются.

С этим никто и не спорит, но в описании стандартных методов работы с потоками я не нашёл способов передачи параметров внутрь.

Судя по алгоритму, тут проще считать несколько решений параллельно чем одно прараллелить.

/// первый способ
final i = 1;
Threan thread = new Thread(new Runnable(){
  public void run() {
    System.out.println(i);
  }
});
thread.start();
/// второй способ
public class Task implements Runnable{
  private final i;
  public Task(int i) {
    this.i = i;
  }
  public void run() {
    System.out.println(i);
  }
}

Threan thread = new Thread(new Task(1));
thread.start();

Два способа, второй предпочтительнее. Только сами потоки не создавайте, используйте пулы, или jetlang.

То есть когда Вы будете видеть, что все 12 ядер завалены на 100%, чувство глубокого удовлетворения от сего факта позволит закрыть глаза на то, что программа стала работать в разы дольше?;-)

Попробуйте-ка ответить себе на след вопросы - сколько тактов на ячейку на итерацию уходит? Сколько данных в ячейке сетки?

Или просто запустите одновременно 12 экземляров, так что бы суммарный размер их данных был равен целевому размеру задачи, и посмотрите что будет с темпом счета (число тактов на ячейку на итерацию). И имейте ввиду, что за счет синхронизаций Вы для одной параллельной задачи такого темпа все равно не получите.

Спасибо за пояснения - теперь понятно как передавать переменные. Но не могу понять как запустить n нитей и каждой передать уникальные параметры.

Естественно нет задачи тупо загрузить проц под завязку. Про количество тактов на ячейки и количество данных в ячейке сказать сложно из-за весьма своеобразного понимания ячейки в этом коде.

А про потери на синхронизацию и прочие пакости я знаю. Одна из целей задачи собственно оценить насколько целесообразно распараллеливание конкретного кода. И без проверки никто не поверит, что надо всё переписывать.

Гугол говорит, что параллелится. Хотя, мне казалось, что во всяких там GSL'ях он и так уже параллельный...

Можно вопрос? Это так принципиально использовать потоки для организации map-reduce? Может проще взять какую-нибудь библиотеку обеспечивающую подобный функционал, например Akka or Hadoop?

Кстати, а почему именно ява? Кроссплатформенность нужна? Так можно же готовые библиотеки использовать...

Это так принципиально использовать потоки для организации map-reduce?

А где там map-reduce?

Да, еще посмотри вот эту доку: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/CountDownLa...

Там хорошо показано как передать данные в потоки, как запустить через тред-пул, и как синхронизироваться на окончании подсчета.

Разделение одного потока данных на кусочки и передача их рабочим потокам, с целью дальнейшего сбора данных и объединения их в конечный результат и есть map-reduce.

Наследственность такая.

Реализация больно своеобразная и вполне вероятен вариант, что допиливание под библиотеки сопоставимо с ручной реализацией (для необходимого функционала).

Хм, ну, наверное да. Я map-reduce понимал более узко.

Это явно не наследственность, а патологический мутаген.

Надо бы это в толксах обсудить :)

Тогда юзаешь следующее

Создаешь вот такую штуку:

CyclicBarrier cyclicBarrier = new CyclicBarrier(NUMBER_OF_THREADS, new ResultComputation());

Потом:

ExecutorService cache = Executors.newCachedThreadPool();

for (/*.....*/) {
    cache.submit(new WorkerThread(cyclicBarrier, someData);
}

cache.shutdown();

По окончанию работы, рабочий поток вызывают метод барьера:

cyclicBarrier.await();

Изначально значение циклического барьера равно 0, как только все потоки закончат свою работу и значение барьера будет равно NUMBER_OF_THREADS, будет создан объект класса ResulComputaton, который в свою очередь соберет все сливки и предоставит результат в удобном для пользователя виде.

Тебе осталось только придумать, как разбить поток данных на кусочки.

Пардон. CyclicBarrier изначально инициализируется значением указанным в конструкторе, а при вызове await уменьшает его значение на 1, пока это значение не достигнет 0 и барьер не будет сброшен.