Книга: Системное программирование в среде Windows

Пример: применение принципа "разделяй и властвуй" для решения задачи сортировки слиянием в SMP-системах

Пример: применение принципа "разделяй и властвуй" для решения задачи сортировки слиянием в SMP-системах

Этот пример демонстрирует возможности значительного повышения производительности за счет использования потоков, особенно в случае SMP-систем. Основная идея заключается в разбиении задачи на более мелкие составляющие, распределении выполнения подзадач между отдельными потоками и последующем объединении результатов для получения окончательного решения. Планировщик Windows автоматически назначит потокам отдельные процессоры, в результате чего задачи будут выполняться параллельно, снижая общее время выполнения приложения.

Эта стратегия, которую часто называют стратегией "разделяй и властвуй" (divide and conquer), или моделью рабочей группы (work crew model), оказалась весьма полезной и в качестве средства повышения производительности, и в качестве метода проектирования алгоритмов. Одним из примеров ее применения служит программа grepMT (программа 7.1), в которой для каждой файловой операции ввода/вывода и для поиска шаблона создается отдельный поток. Как показано в приложении B, в случае SMP-систем производительность повышается, поскольку планировщик может распределять выполнение потоков между различными процессорами.

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

Решение задачи сортировки слиянием (merge-sort), в которой сортируемый массив разбивается на несколько массивов меньшего размера, является классическим примером алгоритма, построенного на принципе "разделяй и властвуй". Каждый из массивов небольшого размера сортируется по отдельности, после чего отсортированные массивы попарно объединяются с образованием отсортированных массивов большего размера. Описанное слияние массивов попарно осуществляется вплоть до завершения всего процесса сортировки. В общем случае, сортировка слиянием начинается с массивов размерности 1, которые сами по себе не нуждаются в сортировке. В данном примере сортировка начинается с массивов большей размерности, чтобы на каждый процессор приходилось по одному массиву. Блок-схема используемого алгоритма показана на рис. 7.2.

Детали реализации представлены в программе 7.2. Число задач задается пользователем в командной строке. Временные показатели сортировки приведены в приложении В. В упражнении 7.9 вам предлагается изменить программу sortMT таким образом, чтобы она сначала определяла количество доступных процессоров, используя для этого функцию GetSystemInfo, а затем создавала по одному потоку для каждого процессора.

Заметьте, что эта программа эффективно выполняется в однопроцессорных системах, в которых имеется достаточно большой запас оперативной памяти, и обеспечивает значительное повышение производительности в SMP-системах. Предостережение. Представленный алгоритм будет корректно работать лишь при условии, что число записей в сортируемом файле нацело делится на число потоков, а число потоков выражается степенью 2. В упражнении 7.8 упомянутые ограничения снимаются.

/* Глава 7. SortMT.
   Сортировка файлов с использованием нескольких потоков (рабочая группа).
   sortMT [параметры] число_задач файл */
#include "EvryThng.h"
#define DATALEN 56 /* Данные: 56 байт; ключ: 8 байт. */
#define KEYLEN 8
typedef struct _RECORD {
 CHAR Key[KEYLEN];
 TCHAR Data[DATALEN];
} RECORD;
#define RECSIZE sizeof (RECORD)
typedef RECORD * LPRECORD;
typedef struct _THREADARG { /* Аргумент потока */
 DWORD iTh; /* Номер потока: 0, 1, 2, … */
 LPRECORD LowRec; /* Младшая часть указателя записи */
 LPRECORD HighRec; /* Старшая часть указателя записи */
} THREADARG, *PTHREADARG;
static int KeyCompare(LPCTSTR, LPCTSTR);
static DWORD WINAPI ThSort(PTHREADARG pThArg);
static DWORD nRec; /* Общее число записей, подлежащих сортировке. */
static HANDLE* ThreadHandle;
int _tmain(int argc, LPTSTR argv[]) {
 HANDLE hFile;
 LPRECORD pRecords = NULL;
 DWORD FsLow, nRead, LowRecNo, nRecTh, NPr, ThId, iTh;
 BOOL NoPrint;
 int iFF, iNP;
 PTHREADARG ThArg;
 LPTSTR StringEnd;
 iNP = Options(argc, argv, _T("n"), &NoPrint, NULL);
 iFF = iNP + 1;
 NPr = _ttoi(argv[iNP]); /* Количество потоков. */
 hFile = CreateFile(argv[iFF], GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL);
 FsLow = GetFileSize(hFile, NULL);
 nRec = FsLow / RECSIZE; /* Общее число записей. */
 nRecTh = nRec / NPr; /* Количество записей на один поток. */
 /* Распределить память для аргументов потока и массива дескрипторов и выделить в памяти место для файла. Считать весь файл. */
 ThArg = malloc(NPr * sizeof(THREADARG));
 /* Аргументы потоков. */
 ThreadHandle = malloc(NPr * sizeof(HANDLE));
 pRecords = malloc(FsLow + sizeof(TCHAR));
 ReadFile(hFile, pRecords, FsLow, &nRead, NULL);
 CloseHandle(hFile);
 LowRecNo = 0; /* Создать потоки, выполняющие сортировку. */
 for (iTh = 0; iTh < NPr; iTh++) {
  ThArg[iTh].iTh = iTh;
  ThArg[iTh].LowRec = pRecords + LowRecNo;
  ThArg[iTh].HighRec = pRecords + (LowRecNo + nRecTh);
  LowRecNo += nRecTh;
  ThreadHandle[iTh] = (HANDLE)_beginthreadex (NULL, 0, ThSort, &ThArg[iTh], CREATE_SUSPENDED, &ThId);
 }
 for (iTh = 0; iTh < NPr; iTh++) /* Запустить все потоки сортировки. */
  ResumeThread(ThreadHandle [iTh]);
 WaitForSingleObject(ThreadHandle[0], INFINITE);
 for (iTh = 0; iTh < NPr; iTh++) CloseHandle(ThreadHandle [iTh]);
 StringEnd = (LPTSTR)pRecords + FsLow;
 *StringEnd = '';
 if (!NoPrint) printf("n%s", (LPCTSTR)pRecords);
 free(pRecords);
 free(ThArg);
 free(ThreadHandle);
 return 0;
 } /* Конец tmain. */
static VOID MergeArrays(LPRECORD, LPRECORD);
DWORD WINAPI ThSort(PTHREADARG pThArg) {
 DWORD GrpSize = 2, RecsInGrp, MyNumber, TwoToI = 1;
 LPRECORD First;
 MyNumber = pThArg->iTh;
 First = pThArg->LowRec;
 RecsInGrp = pThArg->HighRec – First;
 qsort(First, RecsInGrp, RECSIZE, KeyCompare);
 while ((MyNumber % GrpSize) == 0 && RecsInGrp < nRec) {
  /* Объединить слиянием отсортированные массивы. */
  WaitForSingleObject(ThreadHandle[MyNumber + TwoToI], INFINITE);
  MergeArrays(First, First + RecsInGrp);
  RecsInGrp *= 2;
  GrpSize *= 2;
  TwoToI *= 2;
 }
 _endthreadex(0);
 return 0; /* Подавить вывод предупреждающих сообщений. */
}
static VOID MergeArrays(LPRECORD p1, LPRECORD p2) {
 DWORD iRec = 0, nRecs, i1 = 0, i2 = 0;
 LPRECORD pDest, p1Hold, pDestHold;
 nRecs = p2 – p1;
 pDest = pDestHold = malloc(2 * nRecs * RECSIZE);
 p1Hold = p1;
 while (i1 < nRecs && i2 < nRecs) {
  if (KeyCompare((LPCTSTR)p1, (LPCTSTR)p2) <= 0) {
   memcpy(pDest, p1, RECSIZE);
   i1++;
   p1++;
   pDest++;
  } else {
   memcpy(pDest, p2, RECSIZE);
   i2++;
   p2++;
   pDest++;
  }
 }
 if (i1 >= nRecs) memcpy(pDest, p2, RECSIZE * (nRecs – i2));
 else memcpy(pDest, p1, RECSIZE * (nRecs – i1));
 memcpy(p1Hold, pDestHold, 2 * nRecs * RECSIZE);
 free (pDestHold);
 return;
} 

Оглавление книги