74

16.Параллельные алгоритмы

Вид занятия – лабораторная работа Цель – исследование методов разработки алгоритмов для проведения параллельных вычислений

Продолжительность – 4 часа

Если считать, что тактовая частота работы процессоров приблизительно соответствует их производительности, то в настоящее время около 100 млн. операций в секунду (МОПС) — это максимально возможная производительность, которая достижима на одном процессоре [10]. Поскольку ежегодно тактовая частота выпускаемых процессоров возрастает, можно надеяться на увеличение максимальной производительности примерно до 106–108 МОПС. Однако эти процессы не имеют линейной экстраполяции во времени в силу молекулярных ограничений. Процессоры с производительностью более 108 МОПС либо будут иметь принципиально иную архитектуру по сравнению с современными процессорами, либо вообще невозможны. Из этого следует, что единственной стратегией развития вычислительной техники является создание многопроцессорных вычислителей. Получается, что параллельные алгоритмы — единственный перспективный способ повышения производительности при решении будущих задач.

Если вы создаете интерактивное приложение с повышенными требованиями к вычислительным ресурсам и хотите, чтобы его формы не зависали и перерисовывались в реальном режиме времени, или если на вашей ПЭВМ несколько процессоров, или если вы создаете клиент-серверное приложение (все в операционных системах Windows), то рекомендуется делать приложение многопоточным.

Применение многопроцессорных систем требует учета и освоения определенной специфики параллельных вычислений. В настоящей лабораторной работе исследуются особенности параллельного программирования для Microsoft Windows.

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

Пример многопоточного приложения

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

1. Для этого создаём новый проект. Переименуем главную форму проекта в frmMain.dfm. Сохраняя проект, соответствующий главной форме модуль unit1 назовём main.pas, имя проекта выберите на своё усмотрение.

2. Поместите на главную форму три компонента TProgressBar. Свойству Max, описывающему максимальное значение шкалы назначьте значение 1000. Под каждым компонентом TProgressBar пристройте элемент управления «флажок» (TCheckBox). И в правой части формы разместите три элемента – ползунка TTrackBar. У соответствующих компо-

Рисунок 16.1. – Главная форма проекта нентов TCheckBox и TTrackBar поменяй-

те значение свойства tag:

75

CheckBox1 и TrackBar1 – tag=1; CheckBox2 и TrackBar2 – tag=2; CheckBox 3 и TrackBar3 – tag=3.

Последние три компонента проекта – метки TLabel будут хорошо смотреться над шкалами

TProgressBar (рис. 16.1).

Рисунок 16.2. – Новый поток

3.С помощью элементов управления TTrackBar мы сможем изменять приоритеты соответствующих потоков. Одновременно выберите все компоненты TTrackBar, и их свойству Max присвойте значение 3. Значение 0 будет соответствовать минимальному приоритету tpIdle, значение 3 – нормальному tpNormal.

4.С настройкой элементов управления покончено. Займёмся потоками. Для этого выберите пункт меню File – New – Other. На вкладке New найдите иконку ThreadObject и нажмите кнопку ОК. Назовите класс создаваемого потока TMyThread (см. рис. 16.2). Вновь созданный модуль

сшаблоном кода потока сохраните под именем ThreadUnit.pas.

5.В соответствии с приведённым ниже листингом внесите изменения в модуль ThreadUnit:

unit ThreadUnit; interface

uses Classes, Windows, SysUtils, StdCtrls, ComCtrls; type

TMyThread = class(TThread) private

{ Private declarations } procedure UpdateControls;

protected

procedure Execute; override; public

ProgressBar : TProgressBar; {поле потока для подключения к TProgressBar}

Lbl : TLabel;	{поле потока для подключения к информационной метке}
end;
implementation

procedure TMyThread.UpdateControls; begin

ProgressBar.Position:=ProgressBar.Position+1;

if ProgressBar.Position>=ProgressBar.Max then ProgressBar.Position:=0; Lbl.Caption:=IntToStr(ReturnValue);

end;

{ TMyThread }

procedure TMyThread.Execute; var I:INTEGER;

begin

WHILE Terminated=FALSE DO

BEGIN

I:=0;

WHILE I<2000000 DO INC(I);//единственная задача цикла затратить процессорное время

ReturnValue:=ReturnValue+1;

76

Synchronize(UpdateControls); //синхронизируемся с методами VCL

END; end; end.

В секции Public потока опубликованы два поля: поле ProgressBar : TProgressBar и поле lbl : TLabel. Они предназначены для организации взаимодействия потока с размещенной на главной форме шкалой и меткой. Основной метод Execute()выполняется до тех пор, пока не будет разрушен вызовом функции Terminate. Внутри метода реализован цикл WHILE I<2000000 DO INC(I), предназначенный только для пожирания времени процессора. В заключении, из тела метода Execute() осуществляется вызов функции Synchronize(UpdateControls), организующего обновление данных в принадлежащих потоку шкале и метке.

6. Оставим модуль потоков в покое, возвратимся к главной форме проекта и опишем ряд методов. В обработчике события OnCreate() формы поместите строки кода создающие и запускающие все три потока.

procedure TfrmMain.FormCreate(Sender: TObject); begin

Thread1:=TMyThread.Create(True);

Thread1.Priority:=tpIdle;

Thread1.ProgressBar:=ProgressBar1;

Thread1.Lbl:=Label1;

Thread2:=TMyThread.Create(True);

Thread2.Priority:=tpIdle;

Thread2.ProgressBar:=ProgressBar2;

Thread2.Lbl:=Label2;

Thread3:=TMyThread.Create(True);

Thread3.Priority:=tpIdle;

Thread3.ProgressBar:=ProgressBar3;

Thread3.Lbl:=Label3;

Thread1.Resume; //запускаем потоки Thread2.Resume;

Thread3.Resume; end;

В момент создания потоков мы связываем их с элементами управления TProgressBar и TLabel. Обращаю внимание на то, что все три экземпляра потока создаются приостановленными и стартуют практически вместе после того, как к ним были применены все настройки.

7. Чтобы не забыть сразу опишем событие закрытия формы, в которой последовательно разрушим все три потока:

procedure TfrmMain.FormClose(Sender: TObject; var Action: TCloseAction); begin

Thread1.Terminate;

Thread2.Terminate;

Thread3.Terminate; end;

8. Настал звёздный час элемента TTrackBar. Выберите любой из этих компонентов и следующим образом опишите его обработчик события OnChange(). Задача компонента – устанавливать приоритет для соответствующего потока.

procedure TfrmMain.TrackBar1Change(Sender: TObject);

var Priority	: TThreadPriority;
begin	позицию ползунка в	значение приоритета}
{преобразуем
CASE (Sender	as TTrackBar).Position of

0	: Priority:=tpIdle;	//фоновый
1	: Priority:=tpLowest;	//выше фонового
2	: Priority:=tpLower;	//низкий

77

3 : Priority:=tpNormal;	//нормальный
end;

{по tag элемента управления выясняем – какому из потоков требуется изменить приоритет}

CASE (Sender as TTrackBar).Tag of

1 : Thread1.Priority:=Priority;

2 : Thread2.Priority:=Priority;

3 : Thread3.Priority:=Priority;

end; end;

Назначьте описанный выше обработчик события OnChange() общим для всех компонентов

TTrackBar.

9. Опишите обработчик события OnClick() любого из компонентов TCheckBox в соответствии с указанным ниже кодом и сделайте его общим для всех компонентов-флажков. Задача этой процедуры – приостановка/продолжение выполнения потока.

procedure TfrmMain. CheckBox1Click(Sender: TObject);

var Suspended:boolean; begin

Suspended:=(Sender as TCheckBox).Checked; CASE (Sender as TCheckBox).Tag of

1	: Thread1.Suspended:=Suspended;
2	: Thread2.Suspended:=Suspended;
3	: Thread3.Suspended:=Suspended;
end;
end;

	Сделайте этот обработчик общим для всех элементов	Рисунок 16.3. – Внешний вид приложения
	TCheckBox. Приложение готово, сохраните его, и смело
	запускайте (см. рис 16.3).

Задание

1. Разработайте многопоточную программу способную осуществить сортировку двумерного массива целых чисел, таким образом, чтобы в результате выполнения программы, все значения в строках были упорядочены. Например:

3	18	67	99
1	7	23	90 .
45	78	91	100
12	17	52	87

В начале работы программа должна позволять пользователю выбирать размерность исходного массива и заполнять массив случайными числами. Алгоритм сортировки выбирается на усмотрение разработчика (см. лаб. работы 4 и 5).

2. Разработайте N-поточную программу способную упорядочить одномерный массив целых чисел. Алгоритм сортировки выбирается на усмотрение разработчика.