Параллельное программирование для ускорения обработки информации - C#
Формулировка задачи:
Мне необходимо выполнить бинаризацию изображения с использованием k-means на 2 кластера.
Делаю я следующим образом:
1. сначала я подготавливаю массив массивов. Чтобы каждая ячейка соответствовала своему потоку. и в каждой ячейке содержались только те данные, которые будет своё ядро обрабатывать. Для оптимизации так сделал.
вот таким образом я раскидываю. Тут вроде ничего интересного. Всё правильно вроде. Просто так код приложил
Затем я выполняю бинаризацию изображения (все точки изображения делю на 2 класса). Приложил код. Вдруг я меряю время неправильно. Мне нужно замерять время выполнения GetBarycentresParallel
Всю функцию GetBarycentresParallel не стал приводить, приведу наиболее значимый её кусок (во этого объявления переменных и прочая ерунда, не сильно нагружающая процессор
Самое интересное - эта строчка. От неё все и зависит.
Вот код функции
Вроде бы самое сложное место распараллелил. Логично, что если 1 ядря, то выполняется, например, 100 секунд, если 2 ядра то 50 секунд, если 3 то 30 и так далее. Естественно, 50 и 30 это идеальные варианты и вполне неплохо было бы, если бы было 60 и 40, как пример. Но у меня совсем не то что надо получается. вот мои результаты. Распараллеливание даже отрицательный эффект по скорости дало почему-то:
Size image {Width=3976, Height=3299} time 34,45929 processors 1
Size image {Width=3976, Height=3299} time 52,25169305 processors 2
Size image {Width=3976, Height=3299} time 49,773416025 processors 3
Size image {Width=3976, Height=3299} time 44,0997120125 processors 4
Size image {Width=3976, Height=3299} time 38,79137545625 processors 5
Size image {Width=3976, Height=3299} time 34,887025578125 processors 6
Size image {Width=3976, Height=3299} time 31,8754485390625 processors 7
Size image {Width=3976, Height=3299} time 29,6087524195313 processors 8
Size image {Width=3976, Height=3299} time 27,7327576597656 processors 9
Size image {Width=3976, Height=3299} time 26,4133148798828 processors 10
Size image {Width=3976, Height=3299} time 25,2272720399414 processors 11
Size image {Width=3976, Height=3299} time 24,6323545199707 processors 12
Процессор i7-3930k. Количество ядер процессора 6, количество потоков процессора 12.
Почему так печально у меня получается со скоростью?
public void IdentifyPointsArray(int iSize, int iThreadCount)
{
iPointPointer = 0; // указатель на текущую точку
_iPointsInEveryThread = iSize / iThreadCount;
_iDivThread = iSize % iThreadCount;
_dPointsArrayParallel = new double[iThreadCount][][];//сюда нужно раскидать точки изображения _dPoints[][]
for (int i = 0; i < iThreadCount; i++)
{
if (iThreadCount - i > 1)
{
_dPointsArrayParallel[i] = new double[_iPointsInEveryThread][];
}
else
{
_dPointsArrayParallel[i] = new double[_iPointsInEveryThread + _iDivThread][];
}
int iPointsInThread = _dPointsArrayParallel[i].Length;
for (int j = 0; j < iPointsInThread; j++)
{
_dPointsArrayParallel[i][j] = new double[3];
//раскидать точки по ячейкам массива точек для потоков
_dPointsArrayParallel[i][j][0] = _dPoints[iPointPointer][0];
_dPointsArrayParallel[i][j][1] = _dPoints[iPointPointer][1];
_dPointsArrayParallel[i][j][2] = _dPoints[iPointPointer][2];
iPointPointer++;
}
}
}Stopwatch stMy = new Stopwatch();
stMy.Reset();
stMy.Start();
kMeansObject.GetBarycentresParallel(j);
stMy.Stop();
dTime[i] = stMy.Elapsed.TotalSeconds;
dSumTime += dTime[i];while (true)
{
iCountSteps++;
//занулить суммы
_dPointsSum[0, 0] = 0;
_dPointsSum[0, 1] = 0;
_dPointsSum[0, 2] = 0;
_dPointsSum[1, 0] = 0;
_dPointsSum[1, 1] = 0;
_dPointsSum[1, 2] = 0;
_iPointsIn0 = 0;
_iPointsIn1 = 0;
////////////////////////////////////////////////////////////////////
//1. определить кластеры по текущим центрам
Parallel.For(0, iThreadsCount, options, IdentifyPointIntoClusterByThreadArray);
dPointsInclust[0] = _iPointsIn0;
dPointsInclust[1] = _iPointsIn1;
//2. Определить новые центры кластеров
//сохранить значения центров кластеров на предыдущем шаге
_dBaryCentresPrevious[0][0] = _dBaryCentres[0][0];
_dBaryCentresPrevious[0][1] = _dBaryCentres[0][1];
_dBaryCentresPrevious[0][2] = _dBaryCentres[0][2];
_dBaryCentresPrevious[1][0] = _dBaryCentres[1][0];
_dBaryCentresPrevious[1][1] = _dBaryCentres[1][1];
_dBaryCentresPrevious[1][1] = _dBaryCentres[1][2];
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 3; j++)
{
//сохраняем значение
_dBaryCentresPrevious[i][j] = _dBaryCentres[i][j];
_dBaryCentres[i][j] = _dPointsSum[i, j] / dPointsInclust[i];
}
}
dTotalSum = EvclidDistance(_dBaryCentres[0], _dBaryCentresPrevious[0]);
dTotalSum += EvclidDistance(_dBaryCentres[1], _dBaryCentresPrevious[1]);
if (iCountSteps > 10)
{
break;
}
}public void IdentifyPointsArray(int iSize, int iThreadCount)
{
iPointPointer = 0; // указатель на текущую точку
_iPointsInEveryThread = iSize / iThreadCount;
_iDivThread = iSize % iThreadCount;
_dPointsArrayParallel = new double[iThreadCount][][];//сюда нужно раскидать точки изображения _dPointe[][]
for (int i = 0; i < iThreadCount; i++)
{
if (iThreadCount - i > 1)
{
_dPointsArrayParallel[i] = new double[_iPointsInEveryThread][];
}
else
{
_dPointsArrayParallel[i] = new double[_iPointsInEveryThread + _iDivThread][];
}
int iPointsInThread = _dPointsArrayParallel[i].Length;
for (int j = 0; j < iPointsInThread; j++)
{
_dPointsArrayParallel[i][j] = new double[3];
//раскидать точки по ячейкам массива точек для потоков
_dPointsArrayParallel[i][j][0] = _dPoints[iPointPointer][0];
_dPointsArrayParallel[i][j][1] = _dPoints[iPointPointer][1];
_dPointsArrayParallel[i][j][2] = _dPoints[iPointPointer][2];
iPointPointer++;
}
}
}
У кого-нибудь есть идеи, почему так может быть?
Решение задачи: «Параллельное программирование для ускорения обработки информации»
textual
Листинг программы
class Program
{
static void Main()
{
double[] array = new double[20 * 1000 * 1000];
for (int i = 0; i < array.Length; i++)
array[i] = 1;
for (int i = 0; i < 5; i++)
{
Stopwatch sw = Stopwatch.StartNew();
Serial(array, 2);
Console.WriteLine("Serial: {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
ParallelFor(array, 2);
Console.WriteLine("Parallel.For: {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
ParallelForDegreeOfParallelism(array, 2);
Console.WriteLine("Parallel.For (degree of parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
CustomParallel(array, 2);
Console.WriteLine("Custom parallel: {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
CustomParallelExtractedMax(array, 2);
Console.WriteLine("Custom parallel (extracted max): {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
CustomParallelExtractedMaxHalfParallelism(array, 2);
Console.WriteLine("Custom parallel (extracted max, half parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);
sw = Stopwatch.StartNew();
CustomParallelFalseSharing(array, 2);
Console.WriteLine("Custom parallel (false sharing): {0:f2} s", sw.Elapsed.TotalSeconds);
Console.ReadKey();
}
}
static void Serial(double[] array, double factor)
{
for (int i = 0; i < array.Length; i++)
{
array[i] = array[i] * factor;
}
}
static void ParallelFor(double[] array, double factor)
{
Parallel.For(
0, array.Length, i => { array[i] = array[i] * factor; });
}
static void ParallelForDegreeOfParallelism(double[] array, double factor)
{
Parallel.For(
0, array.Length, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount },
i => { array[i] = array[i] * factor; });
}
static void CustomParallel(double[] array, double factor)
{
var degreeOfParallelism = Environment.ProcessorCount;
var tasks = new Task[degreeOfParallelism];
for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
{
// capturing taskNumber in lambda wouldn't work correctly
int taskNumberCopy = taskNumber;
tasks[taskNumber] = Task.Factory.StartNew(
() =>
{
for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
i < array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
i++)
{
array[i] = array[i] * factor;
}
});
}
Task.WaitAll(tasks);
}
static void CustomParallelExtractedMax(double[] array, double factor)
{
var degreeOfParallelism = Environment.ProcessorCount;
var tasks = new Task[degreeOfParallelism];
for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
{
// capturing taskNumber in lambda wouldn't work correctly
int taskNumberCopy = taskNumber;
tasks[taskNumber] = Task.Factory.StartNew(
() =>
{
var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
i < max;
i++)
{
array[i] = array[i] * factor;
}
});
}
Task.WaitAll(tasks);
}
static void CustomParallelExtractedMaxHalfParallelism(double[] array, double factor)
{
var degreeOfParallelism = Environment.ProcessorCount / 2;
var tasks = new Task[degreeOfParallelism];
for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
{
// capturing taskNumber in lambda wouldn't work correctly
int taskNumberCopy = taskNumber;
tasks[taskNumber] = Task.Factory.StartNew(
() =>
{
var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
i < max;
i++)
{
array[i] = array[i] * factor;
}
});
}
Task.WaitAll(tasks);
}
static void CustomParallelFalseSharing(double[] array, double factor)
{
var degreeOfParallelism = Environment.ProcessorCount;
var tasks = new Task[degreeOfParallelism];
int i = -1;
for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
{
tasks[taskNumber] = Task.Factory.StartNew(
() =>
{
int j = Interlocked.Increment(ref i);
while (j < array.Length)
{
array[j] = array[j] * factor;
j = Interlocked.Increment(ref i);
}
});
}
Task.WaitAll(tasks);
}
}