Перейти к содержимому

Фотография

Ускорение вычисления двумерного массива большого размера


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 13

#1
batyrLAN

batyrLAN
  • В доску свой
  • 1 722 сообщений
Приветствую
У меня есть небольшая проблемка.
У меня есть двумерный массив размеров 800х600 и мне нужно для каждого ячейки массива присво


double [,] t1=new double[800,600];
double a1;
double a2;
double a3;
for (int i = 0; i < 800; i++)			//|
     {					//|
     for (int j = 0; j < 600; j++)			//|
          {			//|		//|
          a1 = ....;		//|		//|
          a2 = ....;		//| 50 мсек.	//| 40 сек.
          a3 = a1 + a2;		//|		//|
          t1[i, j] = t1[i, j] + a3;	//|		//|
          }					//|
     }					//|
     return t1				//|

А весь этот цикл надо повторить несколько раз (5-10 раз). Итого весь расчёт занимает 5-10 минут, что ни есть хорошо. Ведь наверняка есть способ ускорить этот цикл. Я думал надо созданием многопоточности, но опыта в этом деле пока нету. Пытался таким образом (упрощённый вид)


public double [,] t1=new double[800,600];

Parallel.For(0, 800, mThread);

private void mThread(int i)
{
double a1;
double a2;
double a3;
for (int j = 0; j < 600; j++)
     {			
     a1 = ....;		
     a2 = ....;		
     a3 = a1 + a2;	
     t1[i, j] = t1[i, j] + a3;
     }
}

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

#2
kornel

kornel
  • В доску свой
  • 9 069 сообщений
Конечно сильно зависит от реализации языка, но даже не касаясь мультизадачности быстрее было бы не резервировать память под 3 переменных, не вычислять их каждую, а сделать
t1[i,j] += ....(которое a1)+...(которое a2)
Очень много где a += b работает заметно быстрее, чем a = a+b.
Кроме этого хорошо бы посмотреть в реализации языка функции, подобные той-же array_map из php
  • 0

#3
forspamonly

forspamonly
  • Гость
  • 34 сообщений
а во сколько раз должно было сократиться? ядер у процессора сколько?

если потоки непрерывно считают, а не блокируются на вводе-выводе, то 800 потоков не имеет смысла. как минимум, пока не будет процессора с 800 ядрами. parallel extensions должны использовать оптимальное количество потоков для системы, вряд ли тут можно сделать руками заметно лучше.

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

ну и оптимизировать само вычисление в любом случае стоит попробовать.

Сообщение отредактировал forspamonly: 02.02.2012, 12:02:48

  • 0

#4
batyrLAN

batyrLAN
  • В доску свой
  • 1 722 сообщений

Конечно сильно зависит от реализации языка, но даже не касаясь мультизадачности быстрее было бы не резервировать память под 3 переменных, не вычислять их каждую, а сделать

t1[i,j] += ....(которое a1)+...(которое a2)
Очень много где a += b работает заметно быстрее, чем a = a+b.
Кроме этого хорошо бы посмотреть в реализации языка функции, подобные той-же array_map из php

О-о-о, классная функция array_map! Вот бы найти похожую в Си Шарпе... Наверняка эта функция оптимизирована для работы с большими массивами.

Да, забыл сказать: я пишу на Си Шарп. Использую Visual Studio 2010 с платформой .NET 4.0
Думать... Надо думать...
  • 0

#5
idaa

idaa
  • Частый гость
  • 60 сообщений

А весь этот цикл надо повторить несколько раз (5-10 раз). Итого весь расчёт занимает 5-10 минут, что ни есть хорошо. Ведь наверняка есть способ ускорить этот цикл.

Даже в жутко тормозной Моне, это работает моментально
http://ideone.com/mPAYv
И после 10 запусков будет отрабатывать не более полсекунды.
Может просто чтото не то меряешь? Или цифры не результат измерения, а с потолка прилеплены?

Можно ли как нибудь сделать так, чтобы запустилось 800 потоков, чтобы каждый из них вычислил значения в отдельной строке всего массива?

CUDA. Но зачем?
  • -1

#6
batyrLAN

batyrLAN
  • В доску свой
  • 1 722 сообщений
В общем, задача стоит такая: у меня есть поле, размером 800 на 600 пикселей. В этой области выбрана произвольная точка dMain, ну, допустим, с координатами (400,240). Теперь мне нужно:
1. Найти расстояние r в пикселях от этой точки до каждой другой точки d1[i, j] области.
a1 = d1.X - dMain.X;
a2 = d1.Y- dMain.Y;
r = Math.Pow((Math.Pow(a1, 2) + Math.Pow(a2, 2)), 0.5);

2. На основе полученного значения r для каждой точки d1[i, j] выполняем некие математические действия, широко используя всякие тригонометрические формулы.

3. Итогом будет t1[i, j] += ..... (некие математические действия)
Можно переписать так:

double [,] t1=new double[800,600];
double r;
double a1;
double a2;
double a3;
for (int i = 0; i < 800; i++)
{
for (int j = 0; j < 600; j++)
{
a1 = i - dMain.X;
a2 = j- dMain.Y;
r = Math.Pow((Math.Pow(a1, 2) + Math.Pow(a2, 2)), 0.5);
..........................
t1[i, j] += ................
}
}
return t1


Сообщение отредактировал batyrLAN: 02.02.2012, 14:35:42

  • 0

#7
forspamonly

forspamonly
  • Гость
  • 34 сообщений
формулы в студию.

конкретно для расстояний можно заранее посчитать вдвое больший буфер с концентрическими кольцами, и брать уже посчитанное из него с нужным смещением.
  • 0

#8
r-dreamer

r-dreamer
  • Гость
  • 9 сообщений
Если вам надо что то типа

Можно ли как нибудь сделать так, чтобы запустилось 800 потоков, чтобы каждый из них вычислил значения в отдельной строке всего массива?


И вы используете

Использую Visual Studio 2010 с платформой .NET 4.0


Вам не надо никакого

CUDA.


Используйте TPL http://msdn.microsof...y/dd460717.aspx
Там даже не обязательно понимать как работают и создаются потоки, TPL сделает все за вас
http://msdn.microsof...rallel.for.aspx это хорошо применимо если у вас итерации цикла не зависят друг от друга, а у вас вроде бы так и есть
так же покурите следующие доки
http://msdn.microsof...e/cc163340.aspx
http://habrahabr.ru/blogs/net/109705/
http://www.professor.../level2/2_7.php

ну и в догонку еще
http://www.techdays....ideos/2839.html
http://www.rsdn.ru/a...harp_Part_3.xml

Сообщение отредактировал r-dreamer: 16.02.2012, 11:48:34

  • 0

#9
forspamonly

forspamonly
  • Гость
  • 34 сообщений

Используйте TPL


а что он по-вашему сейчас использует?

Parallel.For(0, 800, mThread);


  • 0

#10
idaa

idaa
  • Частый гость
  • 60 сообщений

Если вам надо что то типа


Можно ли как нибудь сделать так, чтобы запустилось 800 потоков, чтобы каждый из них вычислил значения в отдельной строке всего массива?


И вы используете

Использую Visual Studio 2010 с платформой .NET 4.0


Вам не надо никакого

CUDA.


Используйте TPL ....

Ща икперты мирового уровня нам расскажут как волшебный TPL натягивает 800 потоков на 2 ядра CPU.
Хабрачитатели ... :faceoff:
  • 0

#11
[N]

[N]
  • Частый гость
  • 72 сообщений
r = Math.Pow((Math.Pow(a1, 2) + Math.Pow(a2, 2)), 0.5);
это лучше заменить на:
r = Math.Sqrt(a1 * a1 + a2 * a2);
  • 0

#12
Five sided

Five sided
  • Свой человек
  • 833 сообщений
http://developers.su.../omp-intro.html
почитать
  • 0

#13
Зул

Зул
  • Свой человек
  • 620 сообщений

http://developers.su.../omp-intro.html
почитать

Не, MPICH конечно круто, но не надо думать что на одном компе это будет работать сильно быстрее. Ну какой-то прирост от многоядерности пойдет конечно, но 800 потоков скорее скорость только замедлят.



На вскидку - не использовать sqrt и прочее, а посчитать расстояния один раз и составить таблицу расстояний - примерно то, что говорил forspamonly. Правда не думаю, что будет толк. Скорее всего у тебя сами функции долго выполняются. Загони в профилировщик да посмотри.
Без знания самих функций ничего не оптимизируешь похоже. Кстати, CUDA неплоха для таких целей. Синус и косинус на видеокарте расчитываются одновременно за один такт, насколько я помню.



Даже в жутко тормозной Моне, это работает моментально
http://ideone.com/mPAYv
И после 10 запусков будет отрабатывать не более полсекунды.
Может просто чтото не то меряешь? Или цифры не результат измерения, а с потолка прилеплены?

Похоже что у автора сложные расчты, а ты гоняешь пустой цикл.
  • 0

#14
forspamonly

forspamonly
  • Гость
  • 34 сообщений

http://developers.su.../omp-intro.html
почитать

MPICH конечно круто

у автора топика дотнет. openmp ему недоступен, равно как и mpi, векторные инструкции (mmx/sse/etc.) или любой сравнительно безгеморройный способ использовать gpu.

не знаю что там у дотнетчиков сейчас модно использовать для распределения расчёта на разные машины вместо mpi, наверное жабий hadoop, но для десятиминутной задачи это в любом случае не самый адекватный подход.

Ну какой-то прирост от многоядерности пойдет конечно

для неприлично параллельной задачи (а по описанию похоже на то) прирост по количеству задействованных ядер должен быть практически линейным. во времена дохуядерных процессоров, считать что-то тяжёлое на одном ядре - моветон.
  • 1


Количество пользователей, читающих эту тему: 1

пользователей: 0, неизвестных прохожих: 1, скрытых пользователей: 0

Размещение рекламы на сайте     Предложения о сотрудничестве     Служба поддержки пользователей

© 2011-2022 vse.kz. При любом использовании материалов Форума ссылка на vse.kz обязательна.