В этом семестре в универе по одному из предметов у нас была такая лаба - написать программу, реализующую какой-либо алгоритм с помощью распараллеливания по ядрам процессора. Ну все, разумеется, понимают, что пока нет специального софта, то толку от количества ядер нет, вот мы и займёмся написанием такового, а заодно и посмотрим - насколько будет лучше результат ))))
Для выполнения
поставленной задачи был выбран алгоритм быстрой сортировки:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
- Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
- Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.
- Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
- Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
- Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина
обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу,
терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно
завершится.
В нашей программной реализации массив разбивается на необходимое количество
независимых друг от друга частей (в зависимости от количества ядер
процессора).
Также возможен режим
работы программы без распараллеливания.
По результатам выполнения работы программы, которые выводятся в консоль, видно, что время, затраченное на выполнение процесса сортировки без распараллеливания существенно больше, чем при работе в параллельном режиме (на 4х-ядерном процессоре у нас примерно получилось, что время различается в два раза).
Графики загрузки ядер и быстродействие при выполнении программы можно посмотреть запустив диспетчер задач.
По результатам выполнения работы программы, которые выводятся в консоль, видно, что время, затраченное на выполнение процесса сортировки без распараллеливания существенно больше, чем при работе в параллельном режиме (на 4х-ядерном процессоре у нас примерно получилось, что время различается в два раза).
Графики загрузки ядер и быстродействие при выполнении программы можно посмотреть запустив диспетчер задач.
Листинг 1. Program.cs.using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading;using System.Diagnostics;namespace ConsoleApplication1{class Program{public static int hhhhhhhh=0;static int ProcessorCount;static void Main(string[] args){//количество процессоровProcessorCount = Environment.ProcessorCount;//ProcessorCount = 2;//список, содержащий части массиваConsole.WriteLine("1 - режим без распараллеливания. 2 - режим с распаралливанием. Сделайте выбор:");String s = Console.ReadLine();Random rnd1 = new Random();// 2147483647int n = 150000000;Console.WriteLine("Генерация массива из {0} записей типа integer", n);int[] b = new int[n];GC.Collect();int max = 100;for (int i = 0; i < b.Length; i++)b[i] = rnd1.Next(0, max);Console.WriteLine("Запись в файл");using (System.IO.StreamWriter file = new System.IO.StreamWriter(@"2.txt"))foreach (int t in b)file.Write(t.ToString() + " ");int rrrr = int.Parse(s);massiv y = new massiv(b, 0, n-1, null);if ((rrrr == 1)||(ProcessorCount == 1)){Console.WriteLine("Выполнение сортировки");Stopwatch sw = null;sw = System.Diagnostics.Stopwatch.StartNew();qSort1(y);sw.Stop();var elapsed = sw.ElapsedMilliseconds;Console.WriteLine("Затраченное время: {0}", elapsed);}else{parall(b, n);}Console.WriteLine("Запись в файл");using (System.IO.StreamWriter file = new System.IO.StreamWriter(@"3.txt"))foreach (int t in b)file.Write(t.ToString() + " ");Console.WriteLine("Нажмите любую клавишу для завершения");Console.ReadKey();}static void parall(int[] b, int n){List<massiv> B = new List<massiv>();Console.WriteLine("Разделение по массивам");//ThreadPool.QueueUserWorkItem(new WaitCallback(qSort1), new massiv(b, 0, n));qSortbegin(b, 0, n - 1, 0, B);Stopwatch sw = null;var threads = new List<Thread>();ManualResetEvent[] handles = new ManualResetEvent[B.Count];for (int h = 0; h < B.Count; h++){massiv y = new massiv(new int[B[h].high - B[h].low + 1], 0, B[h].high - B[h].low, null);for (int i = B[h].low; i < B[h].high + 1; i++)y.B[i - B[h].low] = B[h].B[i];B[h] = y;//ThreadPool.QueueUserWorkItem(new WaitCallback(qSort1), B[h]);//threads.Add(thread);Console.WriteLine("B={0}", B[h].high - B[h].low + 1);}Console.WriteLine("Выполнение сортировки");sw = System.Diagnostics.Stopwatch.StartNew();for(int h = 0; h < B.Count; h++){massiv bbbbb = B[h];/*var thread = new Thread(() =>{qSort1(bbbbb);/* if (threads.All(t => t.ThreadState == System.Threading.ThreadState.Stopped)){sw.Stop();var elapsed = sw.Elapsed;}});*/Thread t = new Thread(qqsort);handles[h] = new ManualResetEvent(false);bbbbb.handl = handles[h];t.Start(bbbbb);//threads.Add(thread);}WaitHandle.WaitAll(handles);sw.Stop();String elapsed = sw.ElapsedMilliseconds.ToString();// var action = new Action(() =>// {//Thread.Sleep(50000);Console.WriteLine("Затраченное время: {0}", elapsed);Console.WriteLine("Сбор в один массив");int k = 0;for (int h = 0; h < B.Count; h++){for (int i = 0; i < B[h].B.Length; i++){b[k] = B[h].B[i];k++;}}// });/*var thread1 = new Thread(() =>{qSort1(B[0]);if (threads.All(t => t.ThreadState == System.Threading.ThreadState.Stopped)){sw.Stop();var elapsed = sw.Elapsed;action();}});threads.Add(thread1);var thread2 = new Thread(() =>{qSort1(B[1]);if (threads.All(t => t.ThreadState == System.Threading.ThreadState.Stopped)){sw.Stop();var elapsed = sw.Elapsed;action();}});threads.Add(thread2);var thread3 = new Thread(() =>{qSort1(B[2]);if (threads.All(t => t.ThreadState == System.Threading.ThreadState.Stopped)){sw.Stop();var elapsed = sw.Elapsed;action();}});threads.Add(thread3);var thread4 = new Thread(() =>{qSort1(B[3]);if (threads.All(t => t.ThreadState == System.Threading.ThreadState.Stopped)){sw.Stop();var elapsed = sw.Elapsed;action();}});threads.Add(thread4);*//* foreach (var thread in threads){thread.Start();}*///thread1.Start();B.Clear();threads.Clear();}public struct massiv{public int[] B;public int low;public int high;public ManualResetEvent handl;public massiv(int[] _B, int _low, int _high, ManualResetEvent _handl){B = _B;low = _low;high = _high;handl = _handl;}};static int medial(int[] b, int low, int high){int medial1;decimal s = 0;for (int i = low; i < high+1; i++){s = s + (decimal)b[i];}medial1 = (int) (s / (high - low));int find = 0;int l = Math.Abs(b[low] - medial1);for (int i = low+1; i < high; i++){if(Math.Abs(b[i]-medial1) < l){l = Math.Abs(b[i] - medial1);find = i;}}return find;}static void qSortbegin(int[] A, int low, int high, int k, List<massiv> B){k++;//int max = 100;int i = low;int j = high;int n = medial(A, low, high);int x = A[n];do{while (A[i] < x) ++i;while (A[j] > x) --j;if (i <= j){int temp = A[i];A[i] = A[j];A[j] = temp;i++; j--;}} while (i <= j);//int A1 = A.ToList().FindIndex(q => q == x);//int A1 = j;if (k * 2 == ProcessorCount){if (low < j)B.Add(new massiv(A, low, j, null));if (i < high)B.Add(new massiv(A, j+1, high, null));}else{if (low < j) qSortbegin(A, low, j, k, B);if (i < high) qSortbegin(A, j+1, high, k, B);}}static void qSort1(massiv m){int[] A = m.B;int i = m.low;int j = m.high;massiv m1 = m;int x = A[(m.low + m.high) / 2];do{while (A[i] < x) ++i;while (A[j] > x) --j;if (i <= j){int temp = A[i];A[i] = A[j];A[j] = temp;i++; j--;}} while (i <= j);if (m1.low < j){m = m1;m.B = A; m.high = j;qSort1(m);}if (i < m1.high){m = m1;m.B = A; m.low = i;qSort1(m);}hhhhhhhh++;}static void qqsort(Object state){massiv m = (massiv)state;qSort1(m);m.handl.Set();}}}
