12 октября 2010 в 09:56

Java для HPC. Расчёт скалярного произведения векторов

Java*
Здравствуйте,

Данный пост — продолжение первого поста по теме.


Данный пост является краткой выжимкой из статьи «Java for High Performance Computing», которая будет представлена мной на университетской конференции Томского Политехнического.

Скалярное произведение векторов — сумма всех произведений соответствующих элементов векторов.

Для решения задачи были написаны две программы — на Си (не мной :-) и на Java.

Тестирование обеих программ производилось на суперкомпьютерном кластере «СКИФ-Политех», установленном в Томском политехническом университете и состоящем из 24 узлов по 2 процессора Intel Xeon 5150 2.66 Ghz и 8 Гб оперативной памяти на каждом под управлением Linux SuSE Enterprise версии 10.3.

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

Следует отметить тот момент, что обе программы:
* не оптимизированы;
* используют одну и ту же функциональность (за исключением внутренних особенностей языков).

Поэтому в комментариях всячески приветствуются дополнения.

Теория, необходимая для решения поставленной задачи

В имплементациях MPI для Си и Java существуют два различия, которые могут сначала смутить:
1) В функциях пересылки сообщений первым аргументом в Си идёт объект, в Java — обязательно одномерный массив;
2) Различная последовательность аргументов.

Для расчёта скалярного произведения векторов необходимо решить следующие задачи:

1) Создать два вектора по N элементов каждый и инициализировать значения;
2) Разделить вектора на частички, которые будут разосланы узлам;
3) Разослать частички;
4) Принять частички на узлах;
5) Произвести вычисления;
6) Отослать обратно;
7) Просуммировать и получить результат;
8) Подсчитать время, затраченное на выполнение программы.

По пунктам:
1) Создать два вектора по N элементов каждый и инициализировать значения

Для Си необходимо выделить соответствующий кусок памяти на массивы — malloc(n*sizeof(double)) и в цикле рандомом rand() инициализировать значения. Для Java достаточно просто создать массивы-вектора, объект класса Random (следует отметить, что на создание объектов уходить много времени, будьте осторожны) и, используя данный объект, инициализировать массивы-вектора.

2) Разделить вектора на частички, которые будут разосланы узлам

Для Си и Java решается одинаково:
n = total / numprocs + 1, где
N — количество частичек на один узел,
Total — длина вектора,
numprocs — количество процессов (MPI_COMM_Size) в пуле.

3) Разослать частички;

Используется функция из библиотеки MPI — MPI_Bcast, рассылающая объект по всем процессам в пуле. За спецификациями можно обращаться на сайт производителя.

В результате рассылка массивов в Java выглядит так:

MPI.COMM_WORLD.Bcast(d, 1, 0,MPI.DOUBLE, 0);
MPI.COMM_WORLD.Send(a,0,a.length,MPI.DOUBLE,dest,0);
MPI.COMM_WORLD.Send(b,0,b.length,MPI.DOUBLE,dest,0);


где d — длина кусочка от массивов,
a — первый вектор,
b — второй вектор.

4) Принять частички на узлах
MPI.COMM_WORLD.Recv(a,0,d[0],MPI.DOUBLE,0,0);
MPI.COMM_WORLD.Recv(b,0,d[0],MPI.DOUBLE,0,0);

Без комментариев.

5) Произвести вычисления

for (int i=0; i<d[0];i++){

sum[0]+=a[i]*b[i];
}


6) Отослать обратно; 7) Просуммировать и получить результат;
А вот здесь интересный момент — две задачи объединим в одну. Воспользуемся редуцирующей функцией, которая сама выполнит за нас все необходимые действия — соберёт результаты и сложит их в одномерный массив (не забываем, что в реализации для Java не должно быть простых переменных!) result.
MPI.COMM_WORLD.Reduce(sum,0,result,0,1,MPI.DOUBLE,MPI.SUM,0);


8) Подсчитать время, затраченное на выполнение программы

Для этого используются две встроенные функции, обе врапперы для стандартных функций — MPI.Wtime (wall time). Поставим вызов первой в начале программы и вычисление общего времени выполнения (не вычисления!) программы в конце.

Выводы

Несмотря на все недостатки Java и сильное различие между временем выполнения программ на Си и Java, окончательное решение о выборе того или иного языка программирования может быть принято лишь после тщательного анализа предметной области и ситуации, в которой оказалась группа исследователей. В некоторых случаях, использование Си гораздо более обосновано за счет высшей призводительности и большей ориентированности на железо (следовательно, большей оптимизации всего процесса), в то же время использование Си налагает большую ответственность на программиста, который должен быть достаточно компетентен, чтобы не выпустить ситуацию из-под контроля и не допустить возникновения критических случаев, в которых программа может «утечь» и потащить за собой всю программу. Это очень важный момент в серьёзных исследованиях.

С другой стороны, использование Java также оправдано. Несмотря на потерю производительности, проблемы с вычислениями чисел с плавающей запятой и прочему Java обладает такими достоинствами, как контроль за ситуацией виртуальной машиной, развитый инструментарий по перехвату исключительных ситуаций, низкий порог вхождения для разработки «числодробилки», отсутствие таких сложных и неоднозначных инструментов, как указатели или ручное выделение памяти — всё это может быть достаточным аргументом для выбора Java как языка программирования для разработки параллельных программ для команды исследователей, не имеющей в своем составе компетентного программиста на Си.

Программа на Си
#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <signal.h>

#define MYTAG 1

int myid, j;
char processor_name[MPI_MAX_PROCESSOR_NAME];
double startwtime = 0.0, endwtime;

int main(int argc,char *argv[])
{
int total, n, numprocs, i, dest;
double *a, *b, sum, result;
int namelen;
MPI_Status status;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Get_processor_name(processor_name,&namelen);

if (myid == 0) {
total = atoi(argv[1]);
}

printf("Process %d of %d is on %s\n",
myid, numprocs, processor_name);

startwtime = MPI_Wtime();

n = total / numprocs + 1;
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

a = malloc(n*sizeof(double));
b = malloc(n*sizeof(double));

if ((a == NULL) || (b == NULL)) {
fprintf(stderr,"Error allocating vectors (not enough memory?)\n");
exit(1);
}

if (myid == 0) {
for (dest=1; dest < numprocs; dest++) {
for (i=0; i < n; i++) {
a[i] = 4294967296;//rand();
b[i] = 4294967296;//rand();
}
MPI_Send(a, n, MPI_INT, dest, MYTAG, MPI_COMM_WORLD);
MPI_Send(b, n, MPI_INT, dest, MYTAG, MPI_COMM_WORLD);
}
n = total - n*(numprocs-1);
for (i=0; i < n; i++) {
a[i] = rand();
b[i] = rand();
}
} else {
MPI_Recv(a, n, MPI_INT, 0, MYTAG, MPI_COMM_WORLD, &status);
MPI_Recv(b, n, MPI_INT, 0, MYTAG, MPI_COMM_WORLD, &status);
}

printf("Process %d on node %s starting calc at %f sec\n",
myid, processor_name, MPI_Wtime()-startwtime);

sum = 0.0;
for (i=0; i<n; i++)
sum += a[i]*b[i];

printf("Process %d on node %s ending calc at %f sec\n",
myid, processor_name, MPI_Wtime()-startwtime);
MPI_Reduce(&sum, &result, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

if (myid == 0) {
endwtime = MPI_Wtime();
printf("Answer is %f\n", result);
printf("wall clock time = %f\n", endwtime-startwtime);
fflush(stdout);
}

MPI_Finalize();
return 0;
}


Программа на Java

import mpi.*;
import java.util.*;

public class scalar {

public static void main(String args[]){
MPI.Init(args);

double[] result = new double[1];
int me = MPI.COMM_WORLD.Rank();
int size = MPI.COMM_WORLD.Size();

double startwtime=0.0;
double endwtime=0.0;
int total = 99999999;

int[] d = new int[1];
d[0] = total/size+1;

double[] a = new double[d[0]];
double[] b = new double[d[0]];
Random r = new Random();

MPI.COMM_WORLD.Bcast(d, 1, 0,MPI.INT, 0);

if (me == 0){
startwtime = MPI.Wtime();
for (int dest=1; dest<size;dest++){
for (int i=0; i<d[0]; i++){
a[i] = r.nextDouble();
b[i] = r.nextDouble();
}

MPI.COMM_WORLD.Send(a,0,a.length,MPI.INT,dest,0);
MPI.COMM_WORLD.Send(b,0,b.length,MPI.INT,dest,0);
}

d[0] = total - d[0]*(size-1);
for (int i=0; i<d[0];i++){

a[i] = r.nextDouble();
b[i] = r.nextDouble();
}

} else {

MPI.COMM_WORLD.Recv(a,0,d[0],MPI.INT,0,0);
MPI.COMM_WORLD.Recv(b,0,d[0],MPI.INT,0,0);

}

int[] sum = new int[1];

for (int i=0; i<d[0];i++){

sum[0]+=a[i]*b[i];

}

MPI.COMM_WORLD.Reduce(sum,0,result,0,1,MPI.INT,MPI.SUM,0);

if (me == 0){

System.out.println("answer is"+result[0]+" time of calcs is equal to "+(MPI.Wtime()-startwtime));

}
MPI.Finalize();

}
}



Белоцерковский Александр @ahriman
карма
39,2
рейтинг 46,1
Пользователь
Самое читаемое Разработка

Комментарии (18)

  • 0
    А на сколько в java по сравнению с C производительность теряется?
    • 0
      Примерно в 1-1.5 раз в случае с целыми числами и 1.5-2 — плавающими.
      Этому вопросу отдельный пост будет посвящён с более оптимизированными программами (что очень важно, так как в этой программе на Java не использованы потоки, а они способны резко увеличить производительность), графиками и диаграммами.
  • 0
    А ничего, что у вас кода примерно одинаковое количество получилось в любом случае? В случае с расчётными задачами, насколько мне приходилось с ними встречаться, основная проблема — это далеко не выделение памяти, а правильное использование и реализация алгоритмов и последующая их проверка. К тому же, Си (и C++) очень даже удобны для решения подобных задач, и использование Java тут количество кода и сложность работы не сокращает.
    • 0
      Данные посты несут только одну цель — показать, что есть ещё один инструмент для решения проблем. Данным инструментом пользуются в своих исследованиях люди зарубежом, значит, они это как-то обосновывали.
      Код на Java интуитивно более понятен, нежели на Си. ИМХО.

      Кроме этого, хотелось бы, чтобы эти посты хоть как-то стимулировали людей. Ведь параллельные вычисления — это прекрасная тема, на которой можно одновременно и вести замечательные исследования, и получать серьёзные гранты. Между тем, в России как-то всё вяло с этим.
  • +2
    Несмотря на потерю производительности, плохое соответствие стандартам о вычислениях чисел с плавающей запятой

    А можно поподробнее, каким стандартам Java не соответствует? А то я знаю только IEEE 754, с которым у Java все в порядке.
    Ну, а про несправедливость микробенчмарков на Java можно даже не говорить, настолько это распространенная ошибка.
    • 0
      > А то я знаю только IEEE 754, с которым у Java все в порядке.

      А зачем в Java ключевое слово strictfp знаете? Вот как раз для строгого соответствия. Но всё равно согласен, заявление автора в целом неверно.
      • 0
        Спасибо за уточнение, убрал.
        • +1
          «проблемы с вычислениями чисел с плавающей запятой» — не лучше.
          • 0
            как тогда? «неоднозначность вычислений»? :-)
            • 0
              Никак. Это настолько непринципиальная для большинства задач тонкость, что даже компиляторы Си и Си++ делают точно так же. google: icc fp model strict.
            • 0
              Уберите вообще про проблемы. Нет там таких проблем. Проблемы могут быть только у программистов, делающих неверные допущения. Как уже было отмечено, модификатор strictfp обязует JVM производить вычисления в точности по стандарту. Без него результаты представляются с той точностью, которую обеспечивает FPU, что вполне естественно.
  • 0
    Ни java, ни C в данном случае не используют SSE? То есть ещё в 2-3 раза медленее, чем могло было бы быть.
    • 0
      Именно. Если есть дополнение, как сделать это по-умному, то был бы очень рад почитать!
  • 0
    Данный пост является краткой выжимкой из статьи «Java for High Performance Computing», которая будет представлена мной на университетской конференции Томского Политехнического.


    Данные посты несут только одну цель — показать, что есть ещё один инструмент для решения проблем. Данным инструментом пользуются в своих исследованиях люди зарубежом, значит, они это как-то обосновывали.


    Взаимоисключающие параграфы. Вы просто взяли инструмент, протестировали его на работоспособность (даже не применили; применили — это если бы задача была не детская), и уже — статья!
    • 0
      Хорошо, пусть будет так. Однако я мониторю по долгу работы и из интереса научные конференции в России и вижу, что подобные прикладные статьи, решающие, возможно, детскую (хотя не каждый взрослый или студент скажет, что такое скалярное произведение векторов) задачу, более востребованы, нежели имеющие в крайней степени узкую область. В конце концов, я не являюсь сколь бы то ни было учёным (о чем написано в профиле), и мои статьи на наши конференции являются исключительно прикладными и информационными. За них я уже получал благодарности от наших учёных, которым эти статьи помогли. Только поэтому я ещё пишу их :-)

      Извиняюсь, если вы потратили своё время на прочтение бесполезного материала. Я даже рад, ведь чем больше людей, понимающих тему, от которой я фанатею, тем лучше!

      • 0
        хотя не каждый взрослый или студент скажет, что такое скалярное произведение векторов


        Позвольте уточнить, студент технической специальности? Если да, то считаете ли вы это нормальным? Так можно и «статьи» про «что такое комплексные числа» писать, всё равно большинство людей не понимает, что это такое.
        • 0
          К огромному моему сожалению, но да. Обратите внимание на общее снижение интереса к науке — на конференциях стало меньше людей, на летние школы всё чаще протаскивают не реальных учёных, а «своих», и так далее.
          Статьи про комплексные числа есть и на русском и на английском. Про параллельные вычисления с реальными, хоть и детскими, примерами — по пальцам можно пересчитать. Отсюда и пляшем. В общем-то, я никакой выгоды от этих статей кроме писульки в резюме не получаю, а раз научрук сказал, что это стоит заслать на конференцию как статью, то надо заслать.
          • 0
            Да, я не считаю это нормальным. Это очень плохо. С другой стороны, тем, кто хоть что-то делает, будет больше работы.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.