Мастер-класс "Оптимизация в программировании (Pascal),высокопроизводительные вычисления"

Если участник номинации прислал программы только на второй тур, то его результаты также участвуют в конкурсе
в равных правах. Участие в первом туре дает шанс улучшить свои результаты в оставшиеся дни, опираясь на результаты остальных участников этого тура.

Итоговая таблица результатов публикуется на данном сайте 24 марта 2010 г.Работы присылаются по почтовому адресу nvn@ulstu.ru профессору кафедры ВТ УлГТУ Виктору Николаевичу Негоде.

=====================================

Мастер-класс

"Оптимизация программ по скорости"

Урок 1. Организация измерения времени исполнения программных функций.

Профессор кафедры ВТ УлГТУ Негода Виктор Николаевич: nvn@ulstu.ru

Соглашения о средствах программирования

В стандарт языка Паскаль, как впрочем и в стандарты большинства других  языков программирования высокого уровня,
не входят средства измерения времени исполнения   программных функций. Это значит, что в различных системах
программирования   наиболее целесообразные решения задачи измерения могут быть различными.   В данном уроке
и самом конкурсе "Мастер информационных технологий"   будут использованы средства, ориентированные на применение 
в системе Free Pascal. Такой выбор объясняется просто: Free Pascal свободно   распространяемая система, которая
позволяет транслировать паскаль-программы   в исполняемый машинный код для различных компьютерных архитектур 
и операционных систем.
Найти дистрибутив можно по многим ссылкам,  в том числе по таким:
    http://www.izone.ru/other/programing/free-pascal.htm
    ftp://ftp.freepascal.org/pub/fpc/dist/2.4.0/i386-win32/fpc-2.4.0.i386-wi...

  Часть 1. Базовый механизм измерений

Существуют несколько способов измерить время исполнения программных  функций при программировании на Паскале.
На сайте volvo71.narod.ru/time_count.htm можно найти описание пяти методов.
Наиболее точный метод основан на использовании машинной команды RDTSC,  которая считывает значение счетчика тактов.
В системе программирования Free Pascal для ОС Windows имеется функция   QueryPerformanceCounter, которая запрашивает
значение счетчика тактов и возвращает значение в переменной, ссылка на которую передается в функцию через ее параметр.
Тип переменной для счетичика тактов - int64.

Пусть нам нужно измерить время исполнения подпрограммы-функции  SumSin, которая суммирует значения синуса
для значений от xmin до   xmax с шагом step.
Вот как будет выглядеть программа измерения:

  {==== Измерение времени сложения значений синусов }
  program msumsin1;
  uses Windows;
  var TStart, TFinish: int64;
  {Получение суммы значений синуса для значений аргумента от xmin до xmax с шагом step}
  function SumSin(xmin,xmax,step:real):real;
  var x: real;
  begin
    x := xmin; SumSin := 0;
    repeat
      SumSin := SumSin + sin(x);
      x := x + step;
    until x > xmax;
  end;

  begin
    QueryPerformanceCounter(TStart);
    SumSin(0,1,0.000001);
    QueryPerformanceCounter(TFinish);
    Writeln('Затрачено ', TFinish - TStart, ' тактов' );
  end.

Если выполнить эту программу по несколько раз на разных машинах, то обнаруживаются два интересных обстоятельства. Во-первых, на одной и той же машине мы получаем разные значения времени. Это означает, что на практике целесообразно делать несколько замеров и как-то обрабатывать массив получаемых значений. В работах по оценке времени можно встретить рекомендации, которые предписывают отбрасывать часть   самых больших и самых маленьких значений массива, а для оставшихся элементов выбирать средне-арифметическое. Мы будем дейстовать проще - просто брать минимальное значение из полученных замеров TFinish - TStart. Это соответствует идее конкурса "Выбираем рекордные по скорости вычислений результаты". Кроме того,  наиболее значимые отклонения от минимальной разницы TFinish - TStart порождаются прерыванием нашего приложения на исполнение функций операционной системы. То есть,  часть времени между замерами времени наш компьютер тратит не на реализацию функции SumSin.
Во-вторых, попытка интерпретировать значение счетчика как число тактов работы процессора, прошедших с момента загрузки операционной системы, оказывается неудачной. Чтобы посмотреть, не даст ли более объективную оценку использование непосредственно машинной команды  rdtsc, целесообразно воспользорваться рецептами сайтов Интернет, где эта команда  запускается в паскаль-программе через ассемблерную вставку следующим образом:

		{Функция возвращает 64-разрядный счетчик тактов, прошедших с момента
  загрузки системы}
function rdtsc:Int64;
  begin
    asm
      rdtsc
    end;
  end;

Ниже представлено решение, где организуются многократные измерения и оценка минимума затраченного времени, а также сравнение случаев использования функции QueryPerformanceCounter и команды rdtsc.

		{ Измерение времени сложения значений синусов
  Два метода доступа к счетчику тактов и использование повторов }
  program msumsin2;
  uses Windows;
  var TStart, TFinish, TMin: int64;
      n: Integer;
      sum: Real;
  {Возвращает значение счетчика тактов, полученное машинной командой RDTSC}
 function rdtsc:Int64;
  begin
    asm
      rdtsc
    end;
  end;

  {Получение суммы значений синуса для значений аргумента
   от xmin до xmax с шагом step}
  function SumSin(xmin,xmax,step:real):real;
  var x: real;
  begin
    x := xmin; SumSin := 0;
    repeat
      SumSin := SumSin + sin(x);
      x := x + step;
    until x > xmax;
  end;

  begin
    TMin := 999999999999999;
    for n := 1 to 1000 do
    begin
      QueryPerformanceCounter(TStart);
      sum := SumSin(0,1,0.00001);
      QueryPerformanceCounter(TFinish);
      if TMin > TFinish - TStart then TMin := TFinish - TStart;
    end;
    Writeln('Затрачено ', TMin, ' тактов(min, QueryPerformanceCounter)' );

    TMin := 999999999999999;
    for n := 1 to 1000 do
    begin
      TStart := rdtsc;
      sum := SumSin(0,1,0.00001);
      TFinish := rdtsc;
      if TMin > TFinish - TStart then TMin := TFinish - TStart;
    end;
   Writeln('Затрачено ', TMin, ' тактов(min,RDTSC)' );

  end.

Испытание этой программы показывает, что функция  QueryPerformanceCounter дает большую "кучность" результатов, нежели rdtsc.

Часть 2. Совершенствование механизма измерений

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

Во-первых, нужно обеспечить, чтобы все реализации работали в равных условиях. Например, если требуется оптимизировать такую процедуру сортировки массива, которая модифицирует исходный массив, то для каждой реализации необходимо предварительно сформировать одно и то же содержимое массива. Если этого не сделать, то первая из выполненных реализаций будет работать с неупорядоченным массивом, а последующим достанется уже упорядоченный массив.  Это значит, что перед каждой процедурой измерения потребуется выполнить процедуру инициализации исходного массива.

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

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

Ниже такая процедура названа именем Measure и в нее передаются строковая переменная lab, через которую именуются подвергаемые испытаниям процедуры, а также указатель на функцию MyFunc, которую необходимо подвергнуть испытаниям:

		{Процедура измерения времени исполнения функции Fu}
procedure Measure(lab:String; Fu:MyFunc);
var TStart, TFinish, TMin: int64;
    n: Integer; {повторитель}
begin
  Ini(); {инициализация исходных данных для обработки}
  tmin := 99999999999999;
  for n :=1 to 1000 do
  begin
      QueryPerformanceCounter(TStart);
      Fu;  {вызов заданной для измерения процедуры}
      QueryPerformanceCounter(TFinish);
      if TMin > TFinish - TStart then TMin := TFinish - TStart;
  end;
  Write(lab,': ', TMin, ' тактов. '); {распечатка результатов измерения} 
  Check(); {проверка правильности срабатывания процедуры MyFunc}
end;

В конкретной задаче тип MyFunc может быть таким, что вызов Fu потребует передачу параметров. Очевидно, что процедуры  Ini и Check также зависят от характера обработки, т.е. для каждой группы процедур обработки данных, сравниваемых по быстродействию, требуется разработка своей пары процедур {Ini, Check}. 

В следующем уроке будет приеден пример использования процедуры Measure.

Урок 2.  Оптимизация по времени программы копирования массивов

Профессор кафедры ВТ УлГТУ Негода Виктор Николаевич: nvn@ulstu.ru

Пусть требуется разработать программу быстрого копирования  из одного двумерного массива в другой, причем, первый массив  имеет меньшую размерность как по числу строк, так и по числу столбцов.  Очевидно, что записать a2 := a1 мы не можем, поскольку массивы из-за различия в размерах не принадлежат одному и тому же типу данных. В ходе оптимизации будем не только строить наиболее быструю реализацию процесса копирования, но и сравнивать различные реализации по скорости. Для этого создадим функции Measure, Ini, Check, смысл которых обсуждался в предыдущем уровке.

Первое, что приходит в голову при организации копирования, это использование вложенного цикла с оператором копирования:  a2[i,j] := a1[i,j]. Внешний цикл с параметром i бежит по строкам, а внутренний цикл с параметром j - по столбцам массивов. Даже при таком простом решении у нас есть две реализации: первая использует в качестве индексов массивов глобальные переменные (описанные в секции var в начале программы) , а вторая - локальные переменные (описанные в секции var процедуры копирования). Назовем соответствующие процедуры CpyGlob  и  CpyLoc.

Понятно, что для реализации оператора копирования a2[i,j] := a1[i,j]  паскаль-компилятор должен организовать вычисление адресов  ячеек памяти, где хранятся (i,,j)-тые элементы массивов  a1 и a2.  А вот если бы массивы были одного типа, то допускалось бы присваивание a2 := a1, для которого компилятор имел бы возможность запустить более быстрое копирование кусков памяти с заданными адресами и размером. Использование копирования кусками могло бы иметь место даже тогда, когда размеры строк массивов были бы одинаковыми. Тогда можно было бы строить один цикл копирования по строкам с оператором a2[i] := a1[i].  Однако наши массивы разнотипны по строкам. В то же время, понятно, что блочное копирование для i-х строк массивов теоретически возможно, если бы можно было привести тип строки a2 к типу строки a1. В Паскале нельзя выполнять такое приведение типов, но можно создать указатель на данные, который как раз и представляет собой адрес памяти. Если создать указатель на данные типа строки первого массива и присвоить этому указателю адрес строки a2[i], то тогда адресуемое этим указателем данное по типу станет совпадать со строкой a1[i]. В учебнике по Паскалю либо в интернет легко можно найти все нужные нам конструкции:  p^ - обращение к данному через указатель p;  @a2[i] - адрес памяти, где начинается строка a2[i];  p: ^TRow1 - объявление переменной p как указателя на тип TRow1, который в нашем случае должен совпадать с типом строки первого массива.

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

		{Построчное копирование с использованием указателя}
procedure CpyPoint(var a1: TArr1; var a2:TArr2);
type TRow1 = array[1..Col1] of Integer;
var i: Integer;
    p: ^TRow1;
begin
   for i := 1 to Row1 do
   begin
     p := @a2[i];
     p^ := a1[i];
   end;
end;

Среди рецептов из программистской литературы и на интернет-сайтах можно встретить рекомендацию развернуть циклы, т.е. представить циклический процес через последовательность операторов, где нет циклов. Если попытаться сделать это для процедуры CpyPoint, то вместо цикла с параметром i мы получим последовательность пар таких операторов:

		{Последовательность операторов копирования}
p := @a2[1]; p^ := a1[1];
p := @a2[2]; p^ := a1[2];
p := @a2[3]; p^ := a1[3];
...

Назовем такую процедуру именем  CpyPointNoCicle.

Ниже представлен полный текст программы исследования всех рассмотренных процедур копирования. Если выполнить испытания на разных машинах, то можно обнаружить, что где-то нет разницы между временами исполнения  CpyGlob и CpyLoc/ Всегда CpyPoint в несколько раз быстрее двух первых процедур, а CpyPointNoCicle оказывается самой быстрой.  Правда у этой процедуры имеется недостаток - ее текст зависит от числа строк массива a1. Если этот размер является постоянным, как в нашем примере, то аккуратное разворачивание цикла дает хорошее приращение производительности. Необходимо отметить, что многие современные компиляторы позволяют автоматически разворачивать циклы с константным числом повторений. Для этого необходимо задействовать соответствующие опции оптимизации компилятора.

{ Несколько реализаций копирования  из одного двумерного массива в другой, причем, первый массив имеет меньшую размерность }

		uses Windows;
const {Число строк и столбщов двух массивов}
      Row1 = 20;
      Col1 = 30;
      Row2 = 40;
      Col2 = 40;
      RepWIN = 1000;    { число повторов для фильтрации других задач}

type  {Типы массивов}
      TArr1 = array[1..Row1,1..Col1] of Integer;
      TArr2 = array[1..Row2,1..Col2] of Integer;
      {Тип функции копирования}
      FuCpy = procedure(var a1: TArr1; var a2:TArr2);

var msec, tmin: Cardinal;  {время засечки и минимум среди повторов}
    arr1: TArr1;
    arr2: TArr2;
    st_i,st_j: Integer; {статические индексы}
    count: Longint;     {счетчик повторов для засечки времени}
    cwin:  Integer;     {счетчик повторов для фильтрации влияния Windows}

{Поэлементное копирование с использованием глобальных индексов}
procedure CpyGlob(var a1: TArr1; var a2:TArr2);
begin
  for st_i := 1 to Row1 do
    for st_j := 1 to Col1 do
      a2[st_i,st_j] := a1[st_i,st_j];
end;

{Поэлементное копирование с использованием локальных индексов}
procedure CpyLoc(var a1: TArr1; var a2:TArr2);
var i,j: Integer;
begin
  for i := 1 to Row1 do
    for j := 1 to Col1 do
      a2[i,j] := a1[i,j];
end;

{Построчное копирование с использованием указателя}
procedure CpyPoint(var a1: TArr1; var a2:TArr2);
type TRow1 = array[1..Col1] of Integer;
var i: Integer;
    p: ^TRow1;
begin
   for i := 1 to Row1 do
   begin
     p := @a2[i];
     p^ := a1[i];
   end;
end;

{Построчное копирование с использованием указателя}
procedure CpyPointNoCicle(var a1: TArr1; var a2:TArr2);
type TRow1 = array[1..Col1] of Integer;
var  p: ^TRow1;
begin
     p := @a2[1]; p^ := a1[1];
     p := @a2[2]; p^ := a1[2];
     p := @a2[3]; p^ := a1[3];
     p := @a2[4]; p^ := a1[4];
     p := @a2[5]; p^ := a1[5];
     p := @a2[6]; p^ := a1[6];
     p := @a2[7]; p^ := a1[7];
     p := @a2[8]; p^ := a1[8];
     p := @a2[9]; p^ := a1[9];
     p := @a2[10]; p^ := a1[10];
     p := @a2[11]; p^ := a1[11];
     p := @a2[12]; p^ := a1[12];
     p := @a2[13]; p^ := a1[13];
     p := @a2[14]; p^ := a1[14];
     p := @a2[15]; p^ := a1[15];
     p := @a2[16]; p^ := a1[16];
     p := @a2[17]; p^ := a1[17];
     p := @a2[18]; p^ := a1[18];
     p := @a2[19]; p^ := a1[19];
     p := @a2[20]; p^ := a1[20];

end;

{Для контроля прописываем массивы arr2 нулями, а arr1 ненулями}
procedure ini();
var i,j:Integer;
begin
  for i := 1 to Row1 do
    for j := 1 to Col1 do
      arr1[i,j] := i+j;
  for i := 1 to Row2 do
    for j := 1 to Col2 do
      arr2[i,j] := 0;
end; {ini}

{ Для проверки делаем так, чтобы изначально все элементы arr2
  равнялись нулю, а arr1 отличались от нуля.
  Проверяестя совпадение arr1 и верхнего прямоугольника arr2,
  а также наличие нулей в части arr2, не охваченной копированием}

procedure check();
var i,j:Integer;
    f: boolean;
begin
  f := true;
  for i := 1 to Row1 do
    for j := 1 to Col1 do
      if(arr1[i,j] <> arr2[i,j])
        then f := false;
  for i := Row1+1 to Row2 do
    for j := Col1+1 to Col2 do
      if(arr2[i,j] <> 0)
        then f := false;
  writeln(f);
end; {check}

procedure Measure(lab:String; fu:FuCpy);
var TStart, TFinish, TMin: int64;
    n: Integer;
begin
  ini();
  TMin := 99999999999999;
  for n :=1 to 1000 do
  begin
    QueryPerformanceCounter(TStart);
      fu(arr1,arr2);
    QueryPerformanceCounter(TFinish);
    if TMin > TFinish-TStart then TMin := TFinish-TStart;
  end;
  Write(lab,': ', TMin, ' тактов. '); Check();

end;

begin

  measure('CpyGlob', @CpyGlob);
  measure('CpyLoc',  @CpyLoc);
  measure('CpyPoint',@CpyPoint);
  measure('CpyPointNoCicle',@CpyPointNoCicle);

end.

Урок 3. Алгоритмы криптографии

Доцент кафедры ВТ УлГТУ Мартыно Антон Иванович: mai@ulstu.ru

Содержание урока

Теоретическая часть

1. Основные понятия и термины криптографии
2. Общий вид криптографической системы
3. Понятие хеш-функции
4. Потоковые шифры
   • Использование операции XOR
   • Генераторы псевдослучайных чисел

Практическая часть

1. Реализация генератора псевдослучайных чисел
2. Хеширование пароля
3. Реализация функции шифрования для потокового шифра

Пример задания

1. Пример потокового шифра

Ввиду того, что в уроке используются математические формулы,
не представляемые средствами данного сайта, полный текст урока
в формате doc-файла можно скачать по этой ссылке.