WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     | 1 | 2 || 4 |

«Аннотация В этом документе мы представляем программирование в Scilab1. В первой части мы представляем управление памятью в Scilab. Во второй части мы представляем различные типы данных и анализируем методы ...»

-- [ Страница 3 ] --

4.8 Заметки и ссылки Янн Коллетт (Yann Collette) разработал модуль parameters как инструмент для предоставления тех же возможностей, что и у функций optimset/optimget в Matlab. Он заметил, что функции optimset/optimget нельзя было настроить снаружи: нам приходится модифицировать функции для того, чтобы добавить новую опцию. Вот почему модуль parameters был создан таким образом, который позволяет позволить пользователю управлять столькими опциями, сколько потребуется.

Область видимости переменных представлена в разделе 4.5.1. Эта тема также представлена в [51].

Проблемы с функциями обратного вызова были представлены в разделе 4.6. Эта тема была проанализирована в сообщениях о программных ошибках №7102, №7103 и №7104 [12, 11, 9].

В [50] Энрико Сегре (Enrico Segre) описал несколько возможностей, связанных с функциями.

В разделе 4.3 мы представили шаблон для разработки устойчивых функций. Используя этот шаблон можно сделать код совместимым с соглашением по коду, представленным Пьером Марешалем (Pierre Marchal) в [34].

В разделе 4.3 мы представляем правила написания устойчивых функций. Написание такой устойчивой функции требует большого числа проверок и может привести к дублированию кода. Модуль apifun [8] является экспериментальной попыткой предоставить API для проверки входных аргументов с бльшей простотой.

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

Мы покажем, как использовать функции tic и toc для измерения характеристик алгоритма. Во втором разделе мы анализируем исходный алгоритм и проверяем, что векторизация может кардинально улучшить характеристики, обычно на множитель от 10 до 100, но иногда и более. Затем, мы анализируем методы компилирования и представляем связь между проектированием интерпретатора и характеристиками. Мы представляем возможности профилирования Scilab и даём пример векторизации алгоритма метода исключения Гаусса. Мы представляем принципы векторизации и сравниваем характеристики циклов с характеристиками векторизованных инструкций. В следующем разделе мы представляем различные методы оптимизации, основанные на практических примерах. Мы представляем библиотеки линейной алгебры, используемые в Scilab. Мы представляем числовые библиотеки BLAS, LAPACK, ATLAS и Intel MKL, которые предоставляют оптимизированные функции линейной алгебры и можем увидеть существенную разницу относительно характеристик матричных операций. В последнем разделе мы представляем различные измерения производительности Scilab’а, основанные на подсчёте операций с плавающей запятой.

На рисунке 27 представлены некоторые функции Scilab, которые используются в контексте анализа характеристик файлов-сценариев Scilab.

5.1 Измерение производительности В этом разделе мы описываем функции, которые позволяют измерить время, требуемое на вычисление. Действительно, перед оптимизацией любой программы нам следует точно измерить её текущую производительность.

В первом разделе мы представляем функции tic, toc и timer. Затем мы сравниваем эти функции и подчёркиваем из отличие на многоядерных машинах. Мы представляем функциональности профилирования в Scilab’е, которые позволяю проанализировать части алгоритма, которые наиболее затратные. Наконец, мы представляем функцию benchfun, которая позволяет провести простой и надёжный анализ производительности.

5.1.1 Основные применения Для того, чтобы измерить время, требуемое на вычисление, мы можем использовать функции tic и toc, которые измеряют пользовательское время в секундах. Пользовательское время время настенных часов, то есть, время, которое требуется компьютеру от начала задачи до её конца. Это включает и само вычисление, конечно, но также все остальные операции системы, такие как обновление экрана, обновление файловой системы, позволение другим процессам делать часть их работы и т. д. В следующем примере мы используем функции tic and toc для измерения времени вычисления собственных значений случайной матрицы на основе функции spec.

--> tic (); lambda = spec ( rand (200,200)); t = toc () Вызов функции tic запускает счётчик, а вызов функции toc останавливает его, возвращая число прошедших секунд. В этом случае мы печатаем инструкции в одной той же строке, используя разделитель ;: действительно, если бы мы напечатали инструкции интерактивно на нескольких строчках, то измеренное время было бы главным образом временем, требуемым на набор инструкций с клавиатуры.

Предыдущее измерение времени не очень надёжно в том смысле, что если бы мы выполнили одни и те же инструкции несколько раз, то не получили бы одного и того же времени. Следующий пример демонстрирует это поведение.

--> tic (); lambda = spec ( rand (200,200)); t = toc () --> tic (); lambda = spec ( rand (200,200)); t = toc () Возможное решение этой проблемы заключается в том, чтобы выполнить одни и то же вычисление несколько раз, скажем, 10 раз, например, и затем распечатать минимальное, максимальное и среднее время.

Предыдущий пример даёт следующий вывод.

Если другая программ на компьютере использует ЦП в то же время, когда Scilab выполняет свои вычисления, то пользовательское время может возрасти. Следовательно функции tic и toc не используются в ситуациях, когда имеет значение только время ЦП. В этом случае мы можем вместо этого использовать функцию timer, которая измеряет время системы. Оно соответствует времени, требуемому ЦП для выполнения специфических вычислений. требуемых Scilab’ом, а не другими процессами.



Следующий пример представляет функцию timer.

The previous script produces the following output.

5.1.2 Пользовательское время и время ЦП В этом разделе мы анализируем разницу между пользовательским временем и временем ЦП на одно- и многоядерных системах.

Давайте рассмотрим следующий файл-сценарий, который позволяет выполнить произведение двух квадратных матриц. Мы измеряем пользовательское время функциями tic и toc, а время ЦП измеряем функцией timer.

disp ([ tUser tCpu tCpu / tUser ]) Следующий пример представляет результат, когда мы запустили этот файл-сценарий на Linux-машине с одним ядром на 2 ГГц.

--> disp ([ tUser tCpu tCpu / tUser ]) Как мы можем видеть два времени довольно близки и показывают, что 91 % времени настенных часов потрачено центральным процессором на конкретное вычисление.

Теперь рассмотрим следующий пример, выполненный на Windows-машине с 4-мя ядрами, где Scilab использует многопотоковую Intel MKL.

--> disp ([ tUser tCpu tCpu / tUser ]) Мы видим что есть существенная разница между временем ЦП и временем настенных часов.

Отношение близко к 4, что равно числу ядер. Действительно, на многоядерной машине, если Scilab использует многопотоковую библиотеку, функция timer сообщает сумму времён, потраченных на каждое ядро. Вот почему во многих ситуациях нам следует использовать функции tic и toc для измерения производительности алгоритма.

5.1.3 Профилирование функции В этом разделе мы представляем возможности профилирования в Scilab’е. Профиль функции раскрывает части функции, которые наиболее затратны. Это позволяет нам сосредоточиться на частях исходного кода, которые наиболее всего требуется улучшить.

Сначала мы рассмотрим исходную, медленную реализацию алгоритма метода исключения Гаусса и проанализируем её профиль. Затем мы используем векторизацию для того, чтобы ускорить вычисления и проанализируем этот обновлённый профиль.

Функции в таблице 28 позволяют управлять профилированием функций.

Рис. 28: Команды Scilab’а для профилирования функций.

В этом разделе мы рассматриваем решение систем линейных уравнений Ax = b, где вещественная матрица размером n n, а b вектор-столбец размером n 1. Одним из наиболее стабильных алгоритмов для этой задачи является метод исключения переменных Гаусса с перестановкой строк. Метод исключения переменных Гаусса с перестановкой строк используется в Scilab’е с помощью оператора обратный слеш \. Для того, чтобы проиллюстрировать профилирование функции, мы не будем использовать оператор обратного слеша. Вместо этого мы разработаем наш собственный алгоритм метода исключения Гаусса (который, очевидно, на практике не является хорошей идеей). Давайте вспомним, что первый шаг алгоритма требует разложить A в виде PA = LU, где P матрица перестановок, L нижняя треугольная матрица, а U верхняя треугольная матрица. Сделав однажды, алгоритмы продолжают выполнение прямого и, затем, обратного исключения.

Алгоритм и короток и сложен, и фактически довольно интересный. Мы не ставим целью получение этого алгоритма через презентацию в этом документе (см. Голуб и Ван Лоан (Golub и Van Loan) [22] для более полного анализа). Этот алгоритм является хорошим кандидатом для профилирования, поскольку он более сложен, чем средняя функция.

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

Следующая функция gausspivotalnaive это простая реализация метода исключения Гаусса с перестановкой строк. Она принимает матрицу A и b в качестве аргумента с правой стороны, и возвращает решение x. Она объединяет разложение PA = LU с прямым и обратным ходом в одной единственной функции. Множители матрицы L сохранены в нижней части матрицы A, а множители матрицы U сохранены в верхней части матрицы 1 function x = gauss pivotalna ive ( A, b ) 3 // Инициализируем перестановку 5 // Выполняем преобразования Гаусса 16 // Перестановка строк k и mu из столбцов от k до n 23 // Выполнение преобразования для строк от k +1 до n 33 // Выполнение прямого хода 45 // Выполнение обратного хода 54 endfunction Перед тем, как действительно измерять производительность, мы должны проверить корректность. поскольку нет смысла делать быстрее функцию, в которой имеются программные ошибки. Это кажется очевидным, но на практике частот не берётся во внимание.

В следующем примере мы формируем матрицу A размером 10 10 со значениями элементов случайно распределёнными на интервале [0, 1). Мы выбрали этот тестовый случай за его очень малое число обусловленности. Мы выбираем ожидаемое решение e с единичными элементами и вычисляем правую сторону b из уравнения b=A*e. Наконец, мы используем нашу функцию gausspivotalnaive для вычисления решения x.

Затем мы проверяем, что число обусловленности матрицы не слишком большое. В следующем примере мы вычисляем число обусловленности матрицы A по 2-норме, и проверяем, что оно приблизительно равно 101, что довольно мал (только порядок величины играет знао чение). Мы также проверим, что относительная ошибка для x имеет ту же амплитуду, что и %eps 1016, что превосходно.

Требовалась бы более полная проверка, но мы сейчас допускаем, что мы можем верить нашей функции.

В следующем примере мы вызовем функцию add_profiling для того, чтобы профилировать функцию gausspivotalnaive.

--> add_profiling ( " ga usspivot alnaive " ) Внимание : переопределение функции : gausspiv otalnaiv e.

Выполните funcprot (0) для отключения этого сообщения Целью функции add_profiling является переопределение функции, которую профилируют, так чтобы Scilab мог сохранить число выполнений каждой строки. Как указано в предупреждении, она в действительности изменяет профилируемую функцию, делая её медленнее.

Это не играет значения, поскольку мы не принимаем слишком серьёзно времена выполнения на графике профиля: мы, вместо этого, будем фокусироваться только на число раз, которое конкретная строчка исходного кода была выполнена.

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

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

plotprofile ( g ausspivo talnaive ) Предыдущий пример формирует фигуру 29. График сделан из трёх гистограмм. Каждая функция имеет 54 строчки, которые представлены на оси X каждой гистограммы. Ось Y зависит от гистограммы. На первой гистограмме ось Y представляет число вызовов (colls) каждой соответствующей строки в профилируемой функции. Это измеряется просто обновлением счётчика каждый раз, когда выполняется строчка. На второй гистограмме ось Y представляет сложность каждой соответствующей строчки в профилируемой функции.

Это измеряет усилия интерпретатора для выполнения соответствующей строчки. Ось Y на третьей гистограмме представляет время ЦП (CPU time), в секундах, требуемое на выполнение соответствующей строчки. На практике, измерение времени ЦП ненадёжно, когда оно недостаточно велико.

Функция plotprofile также открывает редактор и правит профилируемую функцию.

Мышкой мы можем щёлкнуть левой кнопкой на цветные вертикальные полосы гистограммы.

В редакторе это немедленно переместит курсор на соответствующую строчку. Мы сначала щёлкаем левой кнопкой мыши на самую большую полосу, которая соответствует строчке, которая выполнялась более 250 раз. Редактор затем перемещает курсор на строчки № и №24 в нашей функции. Это позволяет немедленно обратиться к следующим строчкам исходного кода.

В оставшейся части этого раздела мы собираемся постоянно использовать профилировщик. Анализируя различные части функции, которые наиболее затратные, мы можем измерить часть, которая имеет наибольшее влияние на производительность. Это позволяет применить принципы векторизации только на строчки исходного кода, которые имеют значение, и позволит нам сохранить большое количество времени. Как только мы это сделаем, мы щёлкаем на меню Exit ( Выход ) в графическом окне, что закрывает график профиля.

Теперь проанализируем предыдущие вложенные циклы по переменным i и j. Мы можем сделать циклы по j быстрее, используя векторизованные инструкции. Используя оператор двоеточие :, мы заменяем переменную j на инструкцию k+1:n, как в следующем примере.

Мы можем распространить принцип далее, и векторизовать также цикл по переменной i, опять же используя оператор двоеточие. Это приводит к следующему исходному коду.

Эффект предыдущей инструкции заключается в обновлении подматрицы A(k+1:n,k+1:n) только одной инструкцией. Ключевым моментом является то, что предыдущая инструкция обновляет множество элементов матрицы только за один вызов Scilab’а.

В данной ситуации, число обновлённых элементов равно (n k)2, что может быть много, если n велико. В общем, мы заменили примерно n2 вызовов обработки интерпретатором матрицы 1 1 одним вызовом обработки матрицы размером n n. Заметим, что умножение A(k+1:n,k)*A(k,k+1:n) это умножение вектора-столбца на вектор-строку, что даёт матрицу размером (n k) (n k) с помощью только одной инструкции.

Аналогично, мы можем векторизовать другие инструкции в алгоритме.

Цикл в следующем исходном коде является очевидным кандидатом на векторизацию.

Предыдущий алгоритм математически эквивалентен, но гораздо медленнее, чем следующая векторизованная инструкция.

Поиск ведущих элементов в следующей части алгоритма кажется менее очевидным кандидатом на векторизацию.

По существу, этот алгоритм является поиском элемента наибольшей величины в одном подстолбце матрицы A. Следовательно, мы можем использовать функцию max, которая возвращает как максимальный элемент её аргумента так и индекс, который получил это максимальное значение. Остаётся комбинировать несколько векторизованных функций для достижения нашей цели, что нетривиально.

Анализируя, как обновляется индекс i во время цикла, мы видим, что рассматриваемая подматрица A(k:n,k). Функция abs работает поэлементно, то есть, выполняет своё вычисление элемент за элементом. Следовательно, инструкция abs(A(k:n,k)) вычисляет абсолютные величины, в которых мы заинтересованы. Мы можем, наконец, вызвать функцию max для выполнения поиска, как в следующем примере.

[ abspivot, murel ]= max ( abs ( A ( k :n, k ))) Заметьте, что функция max выполняет только поиск в части столбца матрицы A. Следовательно переменная murel хранит строку, достигнувшую максимума, относительно блока A(k:n,k). Вот почему мы используем инструкцию mu = murel + k - 1, которая позволяет передать глобальный индекс строки в mu.

Следующий цикл позволяет переставлять строки k и mu матрицы A.

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

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

Действительно, матрица [mu k] является корректной матрицей индексов и может непосредственно использоваться для определения части матрицы A.

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

function x = gausspivotal ( A, b ) // Инициализация перестановок // Выполнение преобразований Гаусса // Сдвиг mu, поскольку max возвращает относительно ( k :n, k ) // Выполнение преобразования для строк от k +1 до n // Выполнение прямого прохода // Выполнение обратного прохода endfunction Ещё раз, мы можем проверить что наша функция работает, как показано в следующем примере.

-->x = gausspivotal ( A, b );

Мы можем обновить профиль, запустив функцию plotprofile с улучшенной функцией gausspivotal. Она формирует фигуру 30.

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

В упражнении 5.1, мы сравниваем действительные производительности этих двух функций. Мы видим, что для матрицы размером 100 100 (что скромно), среднее улучшение производительности может быть более 50. В общем, использование векторизации позволяет улучшить производительность на порядки.

5.1.4 Функция benchfun В этом разделе мы представляем функцию, которая может использоваться для анализа производительности алгоритмов. Мы представляем изменчивость времени ЦП, требуемого для вычисления верхней треугольной матрицы Паскаля и представляем более надёжный способ измерения производительности алгоритма.

Попытаемся измерить производительность следующей функции pascalup_col, которая вычисляет верхнюю матрицу Паскаля.

function c = pascalup_col ( n ) Алгоритм, представленный здесь, основан на постолбцовом доступе к матрице, который особенно быстр, поскольку это именно тот способ, которым Scilab хранит элементы матрицы значений типа double. Эта тема представлена более глубоко в разделе 5.3.6.

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

--> tic (); pascalup_col (1000); toc () --> tic (); pascalup_col (1000); toc () Как мы можем видеть, есть некоторая случайность в измерении затраченного времени. Эта случайность может быть объяснена несколькими фактами, но какие бы причины ни были, нам нужен более надёжный способ измерения времени, требуемого алгоритму. Общий метод заключается в запуске алгоритма несколько раз и усреднении измерений. Этот метод используется в следующем примере. где мы запускаем функцию pascalup_col 10 раз. Затем мы распечатываем минимальное, среднее и максимальное времена, требуемые во время эксперимента.

--> pascalup_col (1000);

Предыдущий метод может быть автоматизирован, что ведёт к функции benchfun, которая представлена ниже. Эта функция запускает алгоритм для которого мы хотим получить надёжные измерения производительности. Входными аргументами являются имя функции name, которую тестируют, функция fun, которую запускают, список iargs, содержащий входные аргументы fun, число выходных аргументов nlhs и число итераций для выполнения kmax. Тело benchfun основано на выполнении функции fun, которая выполняется kmax раз. На каждой итерации измеряется производительность fun на основе функций tic() и toc(), которые измеряют затраченное функцией время (настенные часы). Функция benchfun возвращает матрицу t данных типа double размером kmax1 1, которая содержит различные замеры времени, записанные во время исполнения fun. Она также возвращает строковую переменную msg, которая содержит дружественное к пользователю сообщение, описывающее производительность тестируемого алгоритма.

function [t, msg ] = benchfun ( name, fun, iargs, nlhs, kmax ) // Вычисляем строку инструкции, которую надо запустить // Кладём аргументы левой стороны // Кладём аргументы правой стороны endfunction В следующем примере мы прогоняем функцию pascalup_col 10 раз для того, чтобы получить верхнюю треугольную матрицу Паскаля размером 2000 2000.

--> benchfun ( " pascalup_col ", pascalup_col, list (2000), 1, 10 );

pascalup_col : 10 iterations, mean =0.43162, min =0.41059, max =0. Хотя функцию benchfun можно было бы сделать более устойчивой и более гибкой, этого достаточно для многих случаев. Мы будем часто использовать её в этом разделе.

5.2 Основы векторизации В этом разделе мы представляем основы векторизации. Этот метод программирования является лучшим способом достичь хорошей производительности в Scilab. Первый раздел представляет основы интерпретатора, а также связь между примитивом и шлюзом. Мы сравниваем производительность циклов for с векторизованными инструкциями. В конце мы представляем пример анализа производительности, где мы преобразуем простой, медленный алгоритм в быстрый, векторизованный алгоритм.

5.2.1 Интерпретатор В этом разделе мы кратко представляем методы компилирования так, что мы сможем иметь чёткие представления о значении интерпретатора на вопросы производительности. Мы также представляем связь между интерпретатором и шлюзами, которые являются функциями, которые связывают Scilab с нижележащими библиотеками.

Для того, чтобы понять что именно случается, когда выполняется такая инструкция как y=f(x), мы должны взглянуть на структуру компилятора. Действительно, это позволит нам увидеть связь между инструкциями на уровне интерпретатора и выполнением сносно скомпилированного исходного кода на уровне библиотеки.

Компилятор [5] это программа, которая читает программу на одном языке и переводит её в эквивалентную программу. Если целевая программа является исполнимой, написанной на машинном языке, она может быть вызвана пользователем для обработки входных значений и получения выходных значений. Обычные компиляторы этого типа являются компиляторами Fortran и C/C++ (среди других).

В отличие от предыдущей схемы, Scilab не является компилируемым языком: от интерпретируемый язык. Вместо производства программы на машинном языке, Scilab использует как программу в исходном коде, так и входные данные, и непосредственно производит выходные данные. Рисунок 31 представляет интерпретатор. Распространённые интерпретаторы этого типа Scilab, Matlab и Python (среди прочих).

Программа на машинном языке, сформированная компилятором вообще быстрее, чем программа интерпретатора в преобразовании входных данных в выходные. Интерпретатор, однако, может обычно предоставить лучшую диагностику, чем компилятор, поскольку он исполняет исходный код программы инструкцию за инструкцией. Более того, Scilab использует высокооптимизированные числовые библиотеки, которые в некоторых ситуациях могут быть быстрее, чем простая реализация на основе компилируемого языка. Эта тема будет рассмотрена в разделе 5.4.1, где мы представляем числовые библиотеки линейной алгебры, используемые в Scilab.

Компилятор обычно структурирован как последовательность операций. Первая операция включает в себя чтение символов исходного кода и выполняет лексический анализ.

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

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

Действительно, каждая функция Scilab’а или оператор неодинаково связан с вычислительными процедурами, внедрёнными в компилированный язык, обычно на C или Fortran. Шлюз читает входные аргументы, проверяет их типы и соответствие, выполняет необходимые вычисления и затем выталкивает обратно интерпретатору выходные значения. Такая структура представлена на рисунке 32.

Рис. 32: Scilab связывает интерпретатор с коллекцией библиотек через шлюзы.

5.2.2 Циклы в сравнении с векторизацией В этом разделе мы представляем простой пример векторизации и анализируем почему циклы for являются хорошими кандидатами на векторизацию.

Рассмотрим следующую матрицу значений типа double, состоящую из n = 5 элементов.

Предположим, что мы хотим вычислить сумму 5-ти чисел, хранимых в переменной x.

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

В первом файле-сценарии мы вызываем функцию sum и устанавливаем переменную y.

Это требует только один вызов интерпретатора и включает в себя только один вызов к одному отдельному шлюзу. Внутри шлюза численная библиотека выполняет циклы по n = в компилированном и оптимизированном исходном коде.

Во втором файле-сценарии мы используем циклы for.

Предыдущий файл-сценарий привлекает интерпретатор по крайней мере 2 + n раз, где n размер матрицы x. При n = 5 это 7 вызовов интерпретатора, но линейно возрастает с ростом размера x. Внутри шлюза численная библиотека выполняет одно единственное суммирование каждый раз, когда она вызывается. Когда число циклов большое, то дополнительные затраты на использование инструкции for вместо векторизованной инструкции являются слишком большими.

Поэтому векторизованные инструкции гораздо быстрее циклов. В общем, нам следует делать минимальное количество вызовов интерпретатора и позволить ему работать с достаточно большими наборами данных.

Теперь мы подчеркнём заключение предыдущего обсуждения.

• Если Scilab имеет встроенную функцию, то нам следует рассмотреть её использование до того, как создавать свою собственную. С точки зрения производительности в большинстве случаев они хорошо спроектированы, то есть, они как только возможно используют векторизованные инструкции. Более того, в большинстве случаев они принимают во внимание проблемы чисел с плавающей запятой, так что мы можем получить и быстрое вычисление и хорошую точность.

• Если мы должны создать свой собственный алгоритм, нам следует использовать векторизованные инструкции где только возможно. Действительно, ускорение векторизованных инструкции обычно 10–100, но может быть иногда 1000. В оставшейся части этого документа мы представим несколько примеров улучшения производительности.

Более того, поскольку Scilab может вызывать оптимизированные библиотеки, которые эффективно используют процессор, когда он должен выполнять вычисление с плавающей запятой. Файлы-сценарии Scilab могут быть такими же эффективными как компилированный исходный код, но они могут быть даже быстрее, чем нехитрый компилированный исходный код. Например, библиотеки линейной алгебры, используемые в Scilab’е, берут в расчёт размер кэша процессора и, более того, может выполнять многопотоковые операции. Это центральный момент в Scilab’е, который является преимущественно матричным языком. В разделе 5.4 представлены оптимизированные библиотеки линейной алгебры, используемые в Scilab’е. Не все программы могут получить выгоду от операций линейной алгебры, вот почему мы фокусируемся на методах векторизации, которые можно применять в большинстве ситуаций. Действительно, наш опыт говорит, что векторизация требует некоторой практики. Следующий раздел представляет практический пример анализа производительности на основе векторизации.

5.2.3 Пример анализа производительности В этом разделе мы сравниваем производительность простого и векторизованного алгоритма. Мы проверяем, что ускорение в данном конкретном случае может быть равно 500.

Предположим, что мы имеем вектор-столбец, и что мы хотим вычислить среднее значение этого вектора. У нас две возможности выполнить эту задачу:

• использовать функцию mean, имеющуюся в Scilab, • создать собственный алгоритм.

Функция mean может работать с входными матрицами различных размеров (векторыстроки, векторы-столбцы или общие матрицы) и с различными нормами (1-норма, 2-норма, -норма и норма Фробениуса). Вот почему, в общем, нам не следует переопределять нашу собственную функцию, если в Scilab’е она уже реализована. Более того, производительность функции mean превосходна, как мы увидим. Но в целях иллюстрации вопросов производительности мы разработаем наш собственный алгоритм.

Следующая функция mynaivemean вычисляет среднее значение входного вектора v.

Она выполняет цикл по данным с прямым накоплением суммы.

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

-->y = mynaivemean (1:9) Для того, чтобы проверить наш алгоритм, мы сформируем большие входные векторы v. Для этого, мы используем функцию rand, поскольку мы знаем, что производительность нашего алгоритма не не зависит от действительных значений входного вектора. Мы подчёркиваем эту деталь, поскольку практические алгоритмы могут показывать более или менее быструю производительность в зависимости от своих входных параметров. Сейчас не тот случай, потому что наш анализ упрощённый.

Мы формируем векторы размером n = 10j с j = 1, 2,..., 6. Чтобы сформировать целые числа n, мы используем функцию logspace, которая возвращает значения на основе функции логарифма по основанию 10. Следующий файл-сценарий выполняет циклы от n = до n = 106 и измеряет время, требуемое нашим простым алгоритмом.

n_data = logspace (1,6,6);

ymean = mynaivemean ( v );

Далее представлена распечатка производимая файлом-сценарием.

i =1, n =10, mynaivemean =0.503694, t =0. i =2, n =100, mynaivemean =0.476163, t =0. i =3, n =1000, mynaivemean =0.505503, t =0. i =4, n =10000, mynaivemean =0.500807, t =0. i =5, n =100000, mynaivemean =0.499590, t =0. i =6, n =1000000, mynaivemean =0.500216, t =5. Мы видим, что время растёт очень быстро и является довольно большим для n = 106.

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

i =1, n =10, mean =0.493584, t =0. i =2, n =100, mean =0.517783, t =0. i =3, n =1000, mean =0.484507, t =0. i =4, n =10000, mean =0.501106, t =0. i =5, n =100000, mean =0.502038, t =0. i =6, n =1000000, mean =0.499698, t =0. Как мы видим, функция mean гораздо быстрее нашей функции mynaivemean. В данном случае мы видим, что для n=1000000 отношение по скорости приблизительно 5,25/0,01 = 525.

Для того, чтобы улучшить наш простой алгоритм, мы можем использовать функцию sum, которая возвращает сумму элементов её входного аргумента. Следующая функция myfastmean выполняет вычисление на основе функции sum.

Следующая распечатка представляет производительность нашей улучшенной функции.

i =3, n =1000, mean =0.501551, t =0. i =4, n =10000, mean =0.501601, t =0. i =5, n =100000, mean =0.499188, t =0. i =6, n =1000000, mean =0.499992, t =0. Производительность нашей быстрой функции теперь приблизительно та же, что и производительность встроенной функции mean. В действительности, функция mean является макросом, который выполняет преимущественно тот же самый алгоритм, что и наша функция, то есть он использует функцию sum.

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

Следовательно, цикл, выполняемый Scilab’ом внутри функции sum компилированным исходным кодом. Это действительно быстрее, чем цикл for, выполненный интерпретатором, и объясняет разницу производительностей между нашей и двумя предыдущими реализациями.

5.3 Уловки оптимизации В этом разделе мы представляем общие уловки для получения более быстрых алгоритмов и обратим внимание на использование векторизованных инструкций. Мы представляем опасное использование матриц, чей размер растёт динамически во время работы алгоритма.

Мы представляем функции общего назначения, такие, как векторизованные функции сортировки и поиска, которые могут быть объединены для создания эффективных алгоритмов.

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

5.3.1 Опасность динамических матриц В этом разделе мы анализируем вопросы производительности, которые вызваны использованием матриц, чей размер растёт динамически. Мы показываем числовой эксперимент, где предопределённая матрица известного размера гораздо быстрее матрицы, которой позволено расти динамически.

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

Для того, чтобы проанализировать вопросы производительности, мы сравним три функции с разными реализациями, но с одинаковым выходом. Целью является получение матрицы A=[1,2,3,...,n], где n большое целое число. Чисто в целях эффективности мы могли бы использовать оператор двоеточия : и инструкцию A=(1:n). Для того, чтобы проиллюстрировать конкретный вопрос, который является темой этого раздела, мы не будем использовать оператор двоеточия, а, наоборот, мы используем следующие реализации.

Функция growingmat1 принимает n в качестве входного аргумента и выполняет динамическое вычисление матрицы A. Сначала алгоритм инициализирует матрицу A в виде пустой матрицы. Затем он использует синтаксис $+1 для динамического увеличения размеров матрицы и сохранения нового элемента i.

function growingmat1 ( n ) endfunction Мы не возвращаем матрицу A в качестве выходного аргумента, поскольку это необязательно для нашей демонстрации.

Следующая функция growingmat2 также выполняет динамическое вычисление матрицы A, но использует другой синтаксис. В этот раз матрица динамически обновляется с помощью синтаксиса [A,i], который создаёт новую матрицу-строку с элементом i, добавленным к концу.

function growingmat2 ( n ) endfunction Это создаёт матрицу-строку. Вариант этого алгоритма создавал бы матрицу-столбец синтаксисом [A;i]. Этот вариант не изменит фундаментально поведение алгоритма.

Следующая функция growingmat3 полностью отличается от предыдущих. Вместо инициализации матрицы пустой матрицей, она предварительно создаёт матрицу-столбец нулей.

Затем элементы заполняются один за другим.

function growingmat3 ( n ) В следующем файле-сценарии мы сравниваем производительности трёх предыдущих функций с n=20000 и повторяем замер времени 10 раз для получения более надёжной оценки производительности. Мы используем функцию benchfun, которая была представлена в разделе 5.1.4.

benchfun ( " growingmat1 ", growingmat1, list (20000), 0, 10 );

benchfun ( " growingmat2 ", growingmat2, list (20000), 0, 10 );

benchfun ( " growingmat3 ", growingmat3, list (20000), 0, 10 );

В следующем примере мы получаем замер времени трёх алгоритмов.

growingmat1 : 10 iterations, mean =1. growingmat2 : 10 iterations, mean =0. growingmat3 : 10 iterations, mean =0. Мы видим, что предварительное создание матрицы A с её известным размером n гораздо быстрее. Отношение от самого медленного до самого быстрого более 50.

5.3.2 Линейная индексация матрицы В этом разделе мы покажем как можно получить доступ к обычной матрице с помощью одного-единственного линейного индекса k вместо пары подындексов (i,j). Эта возможность работает как для матриц, так и для гиперматриц, хотя мы в этом разделе рассматриваем только обычных матрицы.

Рис. 33: Линейное индексирование матрицы размером 3 4. Например, значение 21 расположено в ячейке с подындексами (i, j) = (2, 4) и имеет линейный индекс k = 11. Линейные индексы ведут себя так, как если бы элементы были сохранены столбец за столбцом.

Если матрица A имеет m строк, то линейный индекс k, соответствующий подындексам (i, j), равен k = i + (j 1)m. В этом случае инструкции A(i,j) и A(k) эквивалентны. Мы можем понимать эту возможность как следствие того, что матрицы хранятся столбец за столбцом (смотри подробности по этой теме в разделе 5.3.6). В следующем примере мы создаём матрицу значений типа double размером 34. Затем мы обнуляем элемент с линейным индексом k=11. Этот элемент соответствует элементу с подындексами (i, j) = (2, 4).

-->A = matrix (10+(1:12),3,4) Предыдущий пример представлен на рисунке 33.

Функции sub2ind и ind2sub делают преобразование из подындексов в линейные индексы и обратно. Эти функции представлены на рисунке 34. Подчеркнём, что эти функции работают как с матрицами, так и гиперматрицами, но мы остановимся в оставшейся части этого раздела на обычных матрицах.

ind2sub преобразует линейные индексы k в подындексы i1,i2,...

sub2ind преобразует подындексы i1,i2,... линейные индексы k Рис. 34: Функции Scilab’а для преобразования из подындексов в линейные индексы.

Например, мы можем преобразовать линейный индекс в пару подындексов с помощью инструкции [i,j]=ind2sub(dims,k), где dims является матрицей 12, содержащей размеры матрицы. Далее представлен пример функции ind2sub. Рассмотрим матрицу 3 4 (как на рисунке 33) и проверим, что линейный индекс k=11 соответствует подындексам i=2 и j=4.

- - >[i, j ]= ind2sub ([3,4],11) Теперь дадим простой пример как можно использовать функцию sub2ind на практике, когда используется векторизованное вычисление. Допустим, что у нас есть матрица 3 4 и мы хотим обнулить первую диагональ над главной диагональю. В нашем конкретном случае эта диагональ соответствует значениям 14, 18 и 22, которые расположены в строках 1, 2 и 3 и столбцах 2, 3 и 4. Конечно, мы могли бы использовать циклы for, но тогда это не будет векторизованным вычислением. Мы так же не можем напрямую использовать подындексы этих строк и столбцов, поскольку это обнулило бы всю соответствующую подматрицу 3 3, как показано в следующем примере.

-->A = matrix (10+(1:12),3,4) Следовательно, мы используем функцию sub2ind для преобразования этих подындексов в вектор линейных индексов k и затем обнулим эти элементы.

-->A = matrix (10+(1:12),3,4) -->k = sub2ind ([3,4],[1 2 3],[2 3 4]) Предыдущий пример может использоваться в качестве основы для алгоритмов, которые обращаются к диагоналям матриц, таким, как, например, в функции spdiags.

В следующем разделе 5.3.5 мы пересмотрим пример линейного индексирования. Там мы будем использовать функцию find для обращения к отдельным элементам матрицы.

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

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

Предположим, что A является матрицей m n значений типа double, и B является матрицей m n логических значений. Следовательно, инструкция A(B) обращается ко всем элементам A, для которых B равно истине. Это показано в следующем примере, где мы вычисляем все элементы A, которые равны 1, и обнуляем их.

Предыдущая последовательность операций может быть упрощена до одной-единственной инструкции A(A==1)=0. Это показано в следующем примере.

В ситуации, когда поиск отдельных элементов A является слишком сложным, чтобы управляться таким методом, мы можем использовать функцию find, как показано в разделе 5.3.5.

5.3.4 Повтор строк или столбцов вектора В этом разделе мы покажем как создать копии строк или столбцов вектора с помощью векторизованных инструкций.

Интересным свойством матриц является то, что выделение матрицы может быть использовано для повтора элементов одной матрицы. Действительно, если A является матрицей, то мы можем многократно выделять первую строку, что создаёт копии этой строки.

Интересным здесь является то, что создание B не требует циклов: оно векторизовано.

Эта уловка используется в функции repmat, которая может быть интегрирована в Scilab 5.4.

Эта тема изучена в упражнении 5.2.

5.3.5 Комбинирование векторизованных функций Для того, чтобы получить хорошую производительность в Scilab’е, мы можем использовать векторизованные инструкции. В этом разделе мы представляем как комбинировать векторизованные функции.

Векторизованные файлы-сценарии лучше используют оптимизированные библиотеки Scilab’а. Главное правило избегать циклы for.

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

целью этого раздела в том, чтобы представить относительно продвинутые векторизованные функции и подсказать как их комбинировать.

Рисунок 35 представляет наиболее общие векторизованные функции, которые мы можем использовать для получения хорошей производительности.

Рис. 35: Функции Scilab наиболее часто используемые при векторизации.

Алгебраические операторы +, -, *, /, \ представлены здесь из-за того, что они предоставляют превосходную производительность в Scilab’е. Для того, чтобы использовать эти операторы, мы должны сформировать матрицы к которым мы можем применить линейную алгебру. Мы можем использовать zeros, ones и другие матрично-ориентированные функции, но полезный оператор для формирования матриц это произведение Кронекера. В следующем примере мы перемножаем две матрицы размерами 3 2 произведением Кронекера, которое создаёт матрицу размером 4 9.

Произведение Кронекера может быть, например, использовано в комбинаторных алгоритмах, где мы хотим получить комбинации величин из данного набора. Этот вопрос исследован в упражнении 5.2.

Рассмотрим теперь функции find, gsort, min и max, которые имеют специальные входные и выходные аргументы, которые делают их очень полезными, когда мы делаем поиск в быстрых программах.

Использование функции find является общим методом оптимизации, который может заменить алгоритмы поиска. Если B является матрицей m n логических значений, то инструкция k=find(B) возвращает линейные индексы k, для которых B равна истине.

Если поиск завершился неудачно, то есть, если ни один из элементов не соответствует условию, то функция find возвращает пустую матрицу. Можно подумать, что необходимо явно управлять этим конкретным случаем. Однако инструкция A([])=0 ничего не делает, поскольку пустая матрица [] соответствует пустому набору индексов. Следовательно на выходе функции find в большинстве случаев нет нужды обрабатывать случай неудачи отдельной инструкцией if.

В следующем примере мы обнуляем все элементы матрицы A,которые равны 1.

Этот пример можно укоротить объединив функции в одну-единственную инструкцию, как показано ниже.

Поэкспериментируем что будет, если значение, которое мы искали, не найдено.

Конечно, как показано в разделе 5.3.3, мы могли бы использовать более короткую инструкцию A(A==1)=0.

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

Если используются не все элементы, удовлетворяющие условию, а лишь их часть, то мы можем использовать второй входной аргумент функции find. Например, инструкция k=find(A(:,2)>0,1) возвращает первый индекс второго столбца A, который положительный.

Функции min и max могут быть использованы с двумя выходными аргументами. Действительно, инструкция [m,k]=min(A) возвращает минимальное значение m и индекс k элемента в A, который имеет минимальное значение. Другими словами, индекс k такой, что A(k)==m. Например, инструкция [m,k]=min(abs(A)) сочетает функцию min и поэлементную функцию abs. Это позволяет получить индекс k того элемента матрицы A, который имеет минимальное абсолютное значение.

Функция gsort имеет также второй аргумент, который может быть полезен для получения хорошей производительности. Действительно, инструкция [B,k]=gsort(A) возвращает сортированную матрицу B и линейные индексы k элементов в исходной матрице. Другими словами, матрица B такова, что B(:)==A(k). На практике мы можем применять ту же перестановку во второй матрице C с помощью инструкции C = C(k).

5.3.6 Постолбцовое обращение быстрее Мы можем получить бльшую производительность с помощью постолбцового обращео ния к матрице, нежели с помощью построчному. В этом разделе мы представляем пример улучшения производительности с помощью изменения ориентации алгоритма и представим объяснение этому поведению.

Вопрос, который мы собираемся рассмотреть, обсуждался в сообщении об ошибке №7670 [13]. Проблема заключается в вычислении матрицы Паскаля, которая может быть получена из формулы бинома. Ряд отдельных наборов с j элементами, которые могут быть выбраны из набора A с n элементами, является биномиальным коэффициентом и обозначаn ется. Он определяется как Для целых чисел n > 0 и 0 < j < n, биномиальные коэффициенты удовлетворяют Следующие два файла-сценария позволяют вычислить матрицу Паскаля. В первой реализации мы вычисляем нижнюю треугольную матрицу Паскаля и выполняем построчный алгоритм.

// Pascal lower triangular : Row by row version function c = pascallow_row ( n ) endfunction Предыдущая реализация была предложена мне Каликстом Денизетом (Calixte Denizet) в обсуждении, связанном с сообщением о программной ошибке, но похожая идея была представлена Самуэлем Гужоном (Samuel Gougeon) в том же потоке. Во второй реализации мы вычисляем верхнюю треугольную матрицу Паскаля и выполняем постолбцовый алгоритм.

// Pascal upper triangular : Column by column version function c = pascalup_col ( n ) endfunction Следующий пример показывает, что обе реализации математически корректны.

--> pascalup_col (5) --> pascallow_row ( 5 ) Но между двумя этими алгоритмами есть существенная разница в производительности. Рисунок 36 представляет производительность этих двух алгоритмов для различных размеров матриц. Рисунок представляет отношение между постолбцовой и построчной реализациями.

Как видим, постоблцовая реализация в целом на 10 % быстрее построчной реализации. За Рис. 36: Сравнение постолбцового и построчного алгоритмов для матрицы Паскаля.

исключением редких экспериментов, этот факт верен для матриц всех размеров.

Причиной этого является внутренняя структура данных для матрицы чисел типа double, которая ориентирована на Фортран. Поэтому элементы матрицы сохраняются столбец за столбцом как показано на рисунке 37. Следовательно, если мы упорядочим операторы так, что они выполняли постолбцовый алгоритм, то мы будем иметь быстрое обращение к элементам, из-за расположения данных. Это позволяет использовать наилучшим образом процедуру DCOPY (из библиотеки BLAS), которая используется для создания промежуточных векторов, используемых в алгоритме. Действительно, выражение c(2:i,i) создаёт промежуточный вектор-столбец, а выражение c(i,2:i) создаёт промежуточный векторстроку. Это требует создания временных векторов, которые должны заполняться данными, скопированными из матрицы c. Когда вектор-столбец c(2:i,i) создан, то все элементы находятся друг за другом. Вектор-строка c(i,2:i), напротив, требует пропускать все элементы, которые находятся между двумя последовательными элементами в исходной матрице c. Поэтому выделение вектора-строки из матрицы требует большего времени, чем выделение вектора-столбца последовательных элементов: это требует меньше перемещений памяти и лучше использует различные уровни кэша. Следовательно, если данный алгоритм может быть изменён так, чтобы он мог обращаться или обновлять матрицу постолбцово, то следует предпочесть эту ориентацию.

5.4 Оптимизированные библиотеки линейной алгебры В этом разделе мы представляем библиотеки линейной алгебры, которые используются в Scilab’е. В следующем разделе мы представляем BLAS и LAPACK, которые являются Рис. 37: Хранение матрицы чисел типа double размером m n в Scilab. Два последовательных элемента в одном и том же столбце матрицы хранятся последовательно в памяти. Два последовательных элемента в одной строке матрицы разделены в памяти m адресами.

строительными блоками линейной алгебры в Scilab’е. Мы также представляем численные библиотеки ATLAS и Intel MKL. Мы представляем метод установки этих оптимизированных библиотек линейной алгебры в операционных системах Windows и Linux. Мы представляем влияние изменения библиотеки на производительность произведения общих неразреженных матриц.

5.4.1 BLAS, LAPACK, ATLAS и MKL В этом разделе мы вкратце представляем библиотеки BLAS, LAPACK, ATLAS и MKL для того, чтобы иметь общее представление об этих библиотеках. Эти библиотеки используются Scilab’ом для обеспечения максимальной производительности в каждой системе.

Библиотека BLAS (Basic Linear Algebra Subprograms основные подпрограммы линейной алгебры) [2] является коллекцией процедур Фортрана, предоставляющих низкоуровневые операции, такие, как добавление векторов, поэлементное и матричное умножения.

Библиотека BLAS делится на три уровня.

• BLAS уровня 1 выполняет скалярные, векторные и векторно-векторные операции.

• BLAS уровня 2 выполняет матрично-векторные операции.

• BLAS уровня 3 выполняет матрично-матричные операции.

Библиотека LAPACK (Linear Algebra Package пакет линейной алгебры) [3] является коллекцией процедур Фортрана для решения задач линейной алгебры высокого уровня. Это включает в себя решение систем линейных уравнений, решение линейных систем по методу наименьшего квадрата, задачи нахождения собственных значений и задачи нахождения сингулярного значения.

Библиотека ATLAS (Automatically Tuned Linear Algebra Software автоматически настраиваемое программное обеспечение линейной алгебры) [1] предоставляет оптимизированные процедуры линейной алгебры BLAS и небольшой набор процедур, оптимизированных библиотекой LAPACK. Библиотека концентрируется на применении эмпирических методов для обеспечения характеристики переносимости. Библиотека ATLAS предоставляет во многих случаях чувствительное улучшение производительности по сравнению с системами основных BLAS/LAPACK.

Библиотека математического ядра фирмы Intel (Intel Math Kernel Library) [25] является библиотекой высокооптимизированных, широко разветвлённых математических процедур для научно-технических и финансовых приложений, которые требуют максимальной производительности. В данный момент под Windows Scilab использует только процедуры линейной алгебры от MKL взамен BLAS.

В Windows следует выбирать Intel MKL для установки (это сделано по умолчанию для Scilab версии 5). В Linux-системах следует использовать оптимизированную версию библиотеки ATLAS, если производительность играет роль. Эти вопросы рассмотрены в разделах 5.4.3 для Windows и 5.4.4 для Linux.

Библиотеки ATLAS и Intel MKL используют разные методы низкоуровневой оптимизации для получения производительности при вычислениях с плавающей запятой. Этот вопрос ещё раз рассмотрен в следующем разделе.

5.4.2 Методы низкоуровневой оптимизации В этом разделе кратко представлены методы низкоуровневой оптимизации, используемые в численных библиотеках линейной алгебры, таких, как ATLAS и Intel MKL. Представлены различные уровни памяти в компьютере. Рассмотрены алгоритмы, используемые в ATLAS для улучшения использования различных уровней кэша. Кратко представлены наборы инструкций процессоров и используемые оптимизированными библиотеками линейной алгебры.

Главной причиной улучшения производительности векторизованных функций является то, что Scilab способен выполнять вычисления над коллекцией данных вместо обработки каждого вычисления отдельно. Действительно, производительность вычисления значительно зависит от того, насколько ЦП может обращаться к данным, которые доступны в различных типах памяти. От наиболее быстрой до наиболее медленной памяти, используемой в современных компьютерах, это различные уровни кэша (встроенного в сам процессор) и оперативная память (RAM) (здесь мы не рассматриваем жёсткий диск в качестве запоминающего устройства, хотя он может быть включён в управление виртуальной памятью).

Рисунок 38 представляет различные уровни памяти, обычно используемой в компьютере.

Теперь рассмотрим следующий пример, где мы выполняем перемножение матрицы на матрицу.

В соответствующем шлюзе Scilab использует процедуру BLAS DGEMM для того, чтобы выполнить требуемое вычисление. Если пользователь выбрал библиотеки ATLAS или MKL во время инсталляции, то вычисления производятся оптимизированным способом.

Поскольку исходный код Intel MKL не является открытым, то мы не знаем какие точно методы использованы в этой библиотеке. В отличие от него, ATLAS является библиотекой с открытым исходным кодом, и мы можем подробно анализировать его.

Подход ATLAS [54] состоит в изоляции машинно-зависимых параметров процедур, которые имеют дело с выполнением оптимизированного матричного умножения на кристалле с кэшем (т. е. кэшем уровня 1). Перемножение на кристалле автоматически создаётся генератором кода, который использует измерения времени для определения факторов правильной блокировки и развёртывания циклов для выполнения оптимизированного умножения на кристалле.

Матричное умножение раскладывается на две части:

1. высокоуровневое, общего размера умножение вне кристалла, которое платформо-независимо, 2. низкоуровневое, фиксированного размера умножение на кристалле, которое машиннозависимое.

Алгоритм высокого уровня основан на умножении блочных матриц. Предположим, что это матрица размером m n, а B это матрица размером k n. Предположим, что целое число NB, количество блоков, делится на m, n и k. Алгоритма умножения блочных матриц мог бы быть написан на языке Scilab следующим образом.

function C = offchip - blockmatmul (A, B, NB ) endfunction В реализации ATLAS инструкция C(I, J) = C(I, J) + A(I,K)*B(K, J) выполнена с помощью функции умножения на кристалле.

Главным параметром алгоритма вне кристалла является NB, но и другие факторы принимаются во внимание. Действительно, ATLAS может использовать другие реализации этого алгоритма, основанного, например, на другом упорядочивании трёх вложенных циклов.

Во всех этих реализациях цикл по k является всегда самым внутренним циклом. А внешний цикл может быть по m (по строкам в A) и по n (по столбцам в B). Для того, чтобы найти оптимальное значение параметров (включая NB, порядок циклов и другие параметры), ATLAS выполняет автоматизированный эвристический поиск через замеры времени. Для каждого набора исследуемых параметров ATLAS использует генератор кода и измеряет производительность с этими установками. В конечном счёте сохраняется наилучшая реализация и генерируется соответствующий исходный код, затем компилируется.

Умножение на кристалле чувствительно к нескольким факторам, включающим повторное использование кэша, переполнение кэша инструкций, порядок инструкций с плавающей запятой, максимальное количество циклов, проявление возможного распараллеливания и ошибки кэша. Более того, умножение на кристалле может использовать специальные инструкции, доступные процессору, такие, как инструкции множественных данных одной инструкции (SIMD). Эти инструкции позволяют выполнять ту же работу над множественными данными одновременно и встроить распараллеливание данных. Есть несколько наборов инструкций SIMD, включающих • MMX, разработанный фирмой Intel в 1996, • 3DNow!, разработанный фирмой AMD в 1998, • Расширение потоковой SIMD (SSE), разработанное фирмой Intel в 1999, • SSE2, разработанный фирмой Intel в 2001, • SSE3, разработанный фирмой Intel в 2004, • Продвинутые векторные расширения, будущее расширение, предложенное фирмой Intel Например, инструкция MULPD может быть использована для выполнения SIMD-умножения двух пакетных значений с плавающей запятой двойной точности. Похожей инструкцией является ADDPD, которая выполняет суммирование SIMD двух пакетных значений с плавающей запятой двойной точности.

На практике формирование бинарного файла для библиотеки ATLAS может потребовать несколько часов времени ЦП перед тем, как оптимизированные настройки автоматически идентифицируются системой ATLAS.

Эти низкоуровневые методы не является главной заботой пользователей Scilab. Одного это позволяет понимать почему специфичные библиотеки, поставляемые вместе с Scilab’ом, являются разными для Pentium III, Pentium 4 или Dual или Quad Core. Более важно то, что это позволяет знать уровень оптимизации, который мы можем получить от вычислений с плавающей запятой и особенно линейной алгебры, которая является главной целью языка Scilab.

5.4.3 Установка оптимизированных библиотек линейной алгебры для Scilab под В этом разделе мы представляем метод установки оптимизированных библиотек линейной алгебры для Scilab на Windows.

На Windows мы обычно устанавливаем Scilab после его скачивания с http://www.

scilab.org (но некоторые пользователи имеют предустановленный Scilab на своих машинах). Когда мы скачиваем установщик Scilab для Windows и запускаем его, то мы можем выбирать из трёх возможностей:

• Полную установку (по умолчанию), где устанавливаются все модули, • Установку, где некоторые модули отключены, • Выборочную установку, где пользователь может выбирать включение или отключение модулей.

По умолчанию Scilab устанавливается с Intel MKL, но этот выбор может быть настроен пользователем в диалоге установки, который представлен на рисунке 39.

В разделе CPU Optimization for Scilab диалога установки мы можем выбирать между тремя следующими пунктами.

Рис. 39: Выбор библиотеки линейной алгебры под Windows (Scilab v5.2.2). Мы можем выбирать между BLAS, ATLAS и Intel MKL.

• Download Intel Math Kernel Library for Scilab. Эта установка по умолчанию Эта библиотека содержит оптимизированные библиотеки BLAS и набор LAPACK, предоставленный фирмой Intel. Эта библиотека является не полной Intel MKL, а только набором функций, которые используются в Scilab для BLAS и LAPACK.

• Atlas library for Windows. Эта библиотека скомпилирована консорциумом Scilab Consortium для обеспечения оптимальной производительности в широком диапазоне современных компьютеров.

• BLAS, LAPACK Reference library for Windows. Эта библиотека является опорной реализацией, предоставленной http://www.netlib.org/blas и http://www.netlib.org/ Эти опции имеют прямое влияние на две динамических библиотеки, которые хранятся в директории bin Scilab’а:

• bin \blasplus.dll : динамическая библиотека для BLAS, • bin \lapack.dll : динамическая библиотека для LAPACK.

На практике можно иметь одну и ту же версию Scilab’а, установленную с разными библиотеками линейной алгебры. Действительно, несложно настроить директорию установки и затем выбрать конкретную библиотеку, которую желают использовать. Следовательно, можно установить Scilab в три разные директории, в каждой свою конкретную библиотеку, так, что мы можем сравнить их поведение и производительность. Этот метод используется в разделе 5.4.5, где представлена разница производительности между этими тремя библиотеками в Windows на классическом тесте производительности.

5.4.4 Установка оптимизированных библиотек линейной алгебры для Scilab под В этом разделе представлен метод установки оптимизированных библиотек линейной алгебры для Scilab под операционной системой Gnu/Linux.

Под Linux сложнее описать процесс установки, поскольку есть много разных дистрибутивов Linux. Тем не менее есть два основных способа получения Scilab под Linux:

• скачать Scilab с http://www.scilab.org, • использовать систему пакетов дистрибутива Linux, например, Debian, Ubuntu, и т. д...

Какой бы источник ни был, Scilab идёт с Reference BLAS и LAPACK, собранными из http:

//www.netlib.org/blas и http://www.netlib.org/lapack.

Чтобы установить оптимизированную библиотеку ATLAS, мы должны собрать нашу собственную версию ATLAS. Поскольку это несколько сложно и занимает время ЦП (обычно один или два часа сборки), то это рассмотрено в конце этого раздела.

Более простое решение в том, чтобы использовать бинарные файлы из дистрибутива Debian. Бинарные файлы ATLAS в Ubuntu приходят из дистрибутива Debian, так что можно так же получить бинарные файлы ATLAS на Ubuntu. Под Ubuntu мы можем использовать, например, менеджер пакетов Synaptic для установки и удаления бинарных пакетов. В этом libatlas3gf-base ATLAS generic shared, который предоставляется Debian’ом.

Использование бинарного файла оптимизированной библиотеки ATLAS под Linux требует несколько простых изменений вручную, которые мы собираемся описать. В директории scilab/lib/thirdparty мы найдём следующие файлы.

$ ls scilab -5.3.0/ lib / thirdparty -rw -r - -r - - 1 mb mb 6.3 M 2010 -09 -23 14:45 liblapack. so.3 gf. -rw -r - -r - - 1 mb mb 539 K 2010 -09 -23 14:45 libblas. so.3 gf. Когда мы удалим файл libblas.so.3gf.0 из директории установки Scilab’а, то Scilab будет использовать библиотеку BLAS из системы Linux. Следовательно, чтобы убедиться, что Scilab использует библиотеку ATLAS, которую мы уже установили в систему, мы просто удаляем файл libblas.so.3gf.0 как в следующем примере.

$ rm scilab -5.3.0/ lib / thirdparty / libblas. so.3 gf. Для того, чтобы получить хорошую производительность, нам не следует использовать бинарный файл, предоставленный Debian’ом. Вместо этого, следует собрать свою собственную библиотеку ATLAS на конкретную машину, которую мы используем. Это из-за обнаруженных во время сборки конкретных настроек, которые позволяют ATLAS’у улучшить свою производительность. Следовательно, двоичный файл ATLAS, который поставляется в Debian разумно оптимизирован для машины, которую использовал для сборки заведующий пакетом. Он довольно хорошо работает и его легко использовать, но на другой машине не даёт максимальной производительности, которую можно получить.

К счастью, исходные коды доступны на http://math-atlas.sourceforge.net, так что кто угодно в Linux’е может настроить собственную библиотеку ATLAS, чтобы получить хорошую производительность линейной алгебры. Более того, в Debian, процесс сделан гораздо легче, поскольку этот конкретный дистрибутив предоставляет все необходимые инструменты. Более подробно эта тема рассматривается в разделе 5.6.

5.4.5 Пример улучшения производительности В этом разделе представлен простой эксперимент в Windows, который демонстрирует выгоду использования оптимизированной библиотеки линейной алгебры в Scilab’е. В качестве программы проверки производительности системы, мы рассматриваем перемножение двух квадратных, плотных, действительных матриц значений типа double.

Определим в следующем файле-сценарии функцию mymatmul, которая принимает размер матриц n в качестве входного аргумента и выполняет перемножение двух матриц, заполненных единичными элементами.

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

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

Использовался Scilab версии 5.2.2 под Windows XP 32 бита. ЦП AMD Athlon 3200+ на 2 ГГц, и система работает с 1 ГБ памяти. В следующем примере мы выполняем файлсценарий программы проверки производительности с библиотекой Atlas.

matmul : 10 iterations, mean =0.00300, min =0.00000, max =0. matmul : 10 iterations, mean =0.03304, min =0.02002, max =0. matmul : 10 iterations, mean =0.27940, min =0.26037, max =0. matmul : 10 iterations, mean =4.11892, min =4.08587, max =4. Рисунок 40 представляет результаты, которые мы получили от трёх оптимизированных библиотек. Наилучшая производительность получена от Intel MKL, за которой близко следует библиотека Atlas. Производительность библиотеки Reference BLAS-LAPACK очевидно ниже.

Используя оптимизированные библиотеки линейной алгебры, пользователи Scilab’а могут получить быстрые вычисления линейной алгебры. На Windows Scilab поставляется с Intel MKL, которая даёт в большинстве случаев великолепную производительность. Заметим, что эта библиотека коммерческая и предоставляется бесплатно пользователям Scilab, поскольку Рис. 40: Чувствительность производительности перемножения матриц в зависимости от библиотеки линейной алгебры. Проверкой производительности является умножение матрицы на матрицу. Тест выполнялся в Scilab версии 5.2.2 под Windows XP 32 бита. ЦП AMD Athlon 3200+ на 2 ГГц, и система работает с 1 ГБ памяти.

консорциум Scilab Consortium имеет лицензию на Intel MKL. Под Linux Scilab поставляется с библиотекой reference BLAS-LAPACK. Оптимизированные библиотеки Atlas доступны для из любого дистрибутива GNU/Linux. Более того, на GNU/Linux мы можем собрать свою собственную библиотеку Atlas и создать настроенную библиотеку, которая специально настроена на наш компьютер.

5.5 Измерение числа операций с плавающей запятой за секунду Общая практика в информатике заключается в вычислении числа операций с плавающей запятой, которое может быть выполнено в течение одной секунды. Это даёт аббревиатуру ops, что означает FLoating Point Operations by Second (количество операций с плавающей запятой за секунду). В этом разделе мы представляем два стандартных теста производительность в Scilab, включающих в себя вычисление произведения двух плотных матриц и вычисления решения линейных уравнений с помощь LU-разложения. В обоих случаях мы сравниваем производительности библиотек линейной алгебры Reference BLAS, ATLAS и Intel MKL, предоставляемых в Scilab под Windows.

5.5.1 Произведение матрицы на матрицу В этом разделе мы рассматриваем производительность произведения матрицы на матрицу на машине с Windows, с несколькими библиотеками линейной алгебры.

Давайте рассмотрим произведение A и B, двух плотных матриц размером nn, используя оператор *. Число операций с плавающей запятой вычисляется напрямую по формуле:

для i, j = 1, 2,..., n. Чтобы вычислить один элемент Cij матрицы C, приходится выполнять n умножений и n суммирований. В результате, количество операций с плавающей запятой 2n. Поскольку количество элементов в матрице C n2, то общее число операций с плавающей запятой равно 2n3.

В этом случае Scilab использует процедуру DGEMM библиотеки BLAS, которая является частью BLAS уровня 3. Основы этого набора BLAS описаны в [15], где авторы подчёркивают, что общий руководящий принцип заключается в том, что эффективные реализации, вероятно, достигаются уменьшением отношения обмена памяти к арифметическим операциям. Это позволяет полностью использовать векторные операции (если возможно) и позволяет встраивать распараллеливание (если возможно). В случае DGEMM число обращений к памяти равно 3n2, а число операций с плавающей запятой равно 2n3. Следовательно, отношение равно 2n/3, что является одним из наивысших в библиотеки BLAS. Например, отношение скалярного произведения (уровень 1) равно 1, а отношение для матрично-векторного произведения (уровень 2) равно 2. Следовательно, мы ожидаем получить хорошую производительность для процедуры DGEMM.

Более того, в [54] авторы подчёркивают, что многие процедуры BLAS уровня 3 могут быть эффективно реализованы, давая эффективное произведение матрицы на матрицу.

Поэтому хорошая производительность DGEMM является ключевым моментом в общей производительности BLAS. В общем, матрицы A, B и C слишком велики, чтобы уместиться в кэше процессора. Поэтому авторы ATLAS’а [54] предлагают использовать алгоритмы с разделением на блоки. Действительно, можно расположить операторы так, чтобы бльшая о часть операций была выполнена с данными в кэше, с помощью алгоритмов с разделением на блоки.

Для того, чтобы измерить производительность произведения матрицы на матрицу в Scilab, мы используем следующий файл-сценарий. Мы используем генератор случайных чисел rand для получения матриц, чьи элементы вычисляются из функции нормального распределения. Мы знаем, что генератор случайных чисел в основе rand является плохого статистического качества, и что функция grand может быть использована в качестве замены. Но это не имеет значения на производительность произведения матрицы на матрицу, так что мы оставим его для простоты. Множитель 1.e6 в вычислении переменной mflops преобразует флопсы в мегафлопсы.

Программа проверки производительности использовалась в Scilab версии 5.2.2 под Windows XP 32 бита. ЦП AMD Athlon 3200+ на 2 ГГц, и система работает с 1 ГБ памяти.

Мы сравниваем здесь производительности трёх библиотек линейной алгебры, предоставленных в Scilab, то есть Reference BLAS, ATLAS и Intel MKL. Для того, чтобы гарантировать выполнимость замеров времени, нам пришлось выбирать отдельно размеры матриц для различных библиотек. Результаты представлены на рисунке 41.

В этом эксперименте самыми быстрыми библиотеками являются Intel MKL и ATLAS Рис. 41: Производительности умножения действительных, квадратных, плотных матриц в Scilab с различными библиотеками под Windows. Выше лучше.

(свыше 2000 мегафлопсов), что намного быстрее библиотеки Reference BLAS (около мегафлопсов). Размеры матрицы n, которые мы использовали в эксперименте, зависят от действительной производительности библиотек по причине, которую мы сейчас анализируем. Вы выбрали размер n для которого библиотека показывает время от 0,1 секунды до секунд. Главным преимуществом создания как можно более быстрых программ определения производительности является сохранение хорошей воспроизводимости. Действительно, если n слишком мало, то может случиться, что измеренное время t равно нулю. В противоположность этому, библиотека Reference BLAS настолько медленна, что измерение времени растёт так быстро (согласно формуле 2n3 ), что запуск алгоритма для матриц большого размера приводит к очень большим временам, делая процесс замера времени затруднительным на практике.

Теперь сравним действительную производительность библиотек с пиковой производительностью, которую мы можем ожидать для данного конкретного процессора. Процессор AMD Athlon 3200+, кодовое имя Venice2, для сокета 939. Частота процессора 2 ГГц. Если процессор способен выполнить одну операцию с плавающей запятой за цикл, то частота 2 ГГц подразумевает, что пиковая производительность должна быть более 2 гигафлопсов, то есть 2000 мегафлопсов. Предыдущий численный эксперимент показывает, что ATLAS и Intel MKL способны достичь эту производительность и даже чуть больше. Это доказывает, Венеция (прим. перев.) что процессор был способен выполнить от 1 до 2 операций с плавающей запятой на цикл процессора. Этот процессор одноядерный, который поддерживает MMX, 3DNow!, SSE, SSE и SSE3. Тот факт, что процессор поддерживает эти наборы инструкций может объяснить почему действительная производительность была слегка выше 2000 мегафлопсов.

Давайте рассмотрим чувствительность производительности к размеру кэша. Может случиться, что библиотека линейной алгебры покажет повышенную производительность для матриц, которые могут быть полностью сохранены в кэше. Цель библиотек ATLAS и Intel MKL в том, чтобы этого не случилось. Следовательно, производительность не должна зависеть от от размера кэша. Давайте проверим, что это действительно происходит в этом конкретном эксперименте. Кэш данных L1 равен 64 КБ, а кэш L2 равен 512 КБ. Поскольку число операций с плавающей запятой двойной точности требует 8 байт (т. е. 64 бита), то число чисел двойной точности, которое может быть сохранено в кэше L1 равно 64000/8 = чисел двойной точности. Это соответствует плотной, квадратной матрице чисел двойной точности размером 89 89. Кэш L2, с другой стороны, может хранить плотную, квадратную матрицу чисел двойной точности размером 256 256. Поскольку размеры наших матриц варьируются от 500 500 до 2000 2000, то мы видим, что общее число чисел двойной точности не может быть (по большей мере) целиком сохранено в кэше. Следовательно, мы приходим к заключению, что алгоритмы, используемые в Intel MKL и ATLAS не слишком чувствительны к размеру кэша.

5.5.2 Обратный слэш В этом разделе мы измеряем производительность оператора обратный слеш в Scilab’е под Linux.

Этот тест производительности часто называется тест производительности LINPACK, поскольку этот тест был создан при разработке проекта LINPACK. Теста производительности LINPACK используется и сейчас, например, в качестве меры производительности для высокопроизводительных компьютеров, таких, как машины из топа 500 (Top 500) [4], например. Эта библиотека вытеснена BLAS’ом и LAPACK’ом, которые используются в Scilab’е.

Давайте рассмотрим квадратную, плотную, действительную матрицу A размером n n и действительный вектор b размером n 1. Оператор \ позволяет вычислить решение x линейного уравнения A*x=b. Внутри, если матрица хорошо обусловлена, Scilab производит LU-разложение матрицы A, используя перемещение строк. Затем, мы выполняем прямую и обратную подстановки, используя LU-разложение. Эти операции основаны на библиотеке LAPACK, которая, внутри, использует библиотеку BLAS. Точные имена процедур LAPACK, используемых оператором обратного слэша, представлены в разделе 5.6.

Решение систем линейных уравнений является типичным случаем использования библиотек линейной алгебры. Поэтому этот конкретный тест производительности очень часто используется для измерения производительности вычислений с плавающей запятой на конкретной машине [40, 16, 43]. Число операций с плавающей запятой для всего процесса равно n + 2n2. Поскольку это число растёт по закону n3, а число элементов матрицы лишь n2, то мы можем ожидать хорошей производительности в этом тесте.

Следующий файл-сценарий измерить производительность оператора обратного слэша в Scilab’е. Мы настраиваем генератор случайных чисел в функции rand таким образом, что он формирует матрицы с элементами, вычисленными по функции нормального распределения. Наконец, мы вычисляем число операций с плавающей запятой и делим на 1.e6 для того, чтобы получить мегафлопсы.

Мы выполняем этот тест в scilab-5.3.0-beta-4 на Linux Ubuntu 32 бита. Процессор Intel Pentium M с частотой 2 ГГц, оперативная память 1 ГБ. Размер кэша 2 МБ. Процессор поддерживает наборы инструкций MMX, SSE и SSE2. Рисунок 42 представляет производительности Reference BLAS и ATLAS. Версия ATLAS’а, которую мы используем, предоставлена Ubuntu. Из-за практических ограничений эти эксперименты остановлены, когда время, требуемое на выполнение одного оператора обратного слэша, стало больше 8 секунд.

Рис. 42: Производительность решения вещественной, квадратной, плотной, линейной системы уравнений оператором обратного слэша с помощью различных библиотек на Linux.

Как мы можем видеть, библиотека ATLAS улучшает производительность оператора обратного слеша примерно в два раза. Более того, мегафлопсы сильно возрастают с размером матрицы, а производительность библиотеки Reference BLAS кажется остаётся одной и той же. Частота процессора 2 ГГц, это предполагает, что мы можем ожидать пиковую производительность свыше 2000 мегафлопсов. Действительная производительность ATLAS’а на этих матрицах в пределах [1000,1400], что несколько разочаровывает. Поскольку эта производительность возрастает, то пиковая производительность может быть достигнута для бльших матриц, но это здесь не проверялось, поскольку времена возрастают очень быстро, делая эксперименты долгими для выполнения.

5.5.3 Многоядерные вычисления В этом разделе мы покажем, что Scilab может выполнять многоядерные вычисления с плавающей запятой, если мы используем, например, библиотеку линейной алгебры Intel MKL, которая в Windows предоставляется вместе с Scilab’ом.

Мы использовали для этого теста Scilab v5.3.0-beta-4 на операционной системе Windows Vista Ultimate 32 бита. Процессор Intel Xeon E5410 с 4 ядрами на 2,33 ГГц [26, 55]. Процессор может управлять 4 потоками (то есть один поток на ядро) и имеет L2 кэш на 12 МБ. Операционная система может иметь только 4 ГБ физической памяти. Рисунок 43 показывает результаты проверки производительности на перемножении матрицы на матрицу, которое мы уже представили в разделе 5.5.1.

Рис. 43: Производительность произведения матрицы на матрицу на 4-х ядерной системе под Windows с различными библиотеками.

Учитывая, что этот процессор имеет 4 ядра на 2,33 ГГц, мы ожидаем производительность больше 9,33 гигафлопсов. Действительная производительность Intel MKL равна 26, гигафлопса, что указывает на то, что эта библиотека использовала 4 ядра, выполняя 2,8 операции с плавающей запятой за цикл. С другой стороны, библиотеки ATLAS и Ref-BLAS не используют 4 ядра этой машины и дают значительно меньшие результаты.

5.6 Замечания и ссылки В разделе 5.2.3 мы анализировали производительность алгоритма суммирования. Можно было бы указать, что точность суммы зависит от размера данных и конкретных значений в наборе данных. Это проанализировано, например, Уилкинсоном (Wilkinson)[56] и Хайэмом (Higham) [24]. Точнее, можно указать, что набор данных может быть плохообусловлен по отношению к сумме, например, если значения смешанных знаков (то есть, некоторые положительные, а некоторые отрицательные) и очень разных амплитуд. В этом случае мы можем наблюдать, что относительная ошибка суммы может быть большой.

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

Тема, которая тесно связана с векторизацией алгоритмов Scilab’а это индексирование матриц, то есть, выбор набора элементов в матрице. Статья Эддинса (Eddins) и Шура (Shure) [18] фокусируется на этой теме в контексте Matlab R, где авторы представляют индексацию векторов, индексацию матриц с помощью двух подпрограмм, линейную индексацию и логическую индексацию на основе логических выражений. Matlab является зарегистрированной торговой маркой Mathworks.

В разделе 5.2.1 мы представили несколько методов, связанных с принципами компиляции. Классической ссылкой по вопросу компиляторов является Книга дракона3 [5]. Эта книга вводит в проектирование компиляторов, включая лексический анализ, регулярные выражения, машины конечных состояний и методы проверки синтаксиса.

В разделе 5.4.1 мы кратко представили проект ATLAS. Уоли (Whaley) и Донгарра (Dongarra) [53] описывают метод автоматического формирования и оптимизации числового программного обеспечения для процессоров с глубокой иерархией памяти и конвейерных блоков реализации функций.

В разделе 5.1.3 мы представили алгоритм метода исключения Гаусса и заявили, что этот алгоритм (но не конкретная реализация, которую мы представили) используется в Scilab’е в основе оператора обратного слеша. Действительное поведение оператора обратного слэша в Scilab’е следующее. Сначала мы выполним вызов процедуры DGETRF из LAPACK, которая раскладывает матрицу A на PA = LU, где P матрица перестановок, L нижняя треугольная матрица, а U верхняя треугольная матрица. Диагональные элементы L являются единицами. Затем мы вызываем процедуру DGECON из LAPACK, которая аппроксимирует инвертирование числа обусловленности 1-нормы матрицы A. В этом месте есть два варианта. Если число обусловленности матрицы не слишком велико, то система линейных уравнений не является плохобусловленной (это не точно, поскольку обусловленность только аппроксимирована, но алгоритмы делают гипотезу о том, что оценка может быть достоверной). В этом случае мы вызываем процедуру DGETRS из LAPACK, которая решает систему линейных уравнений, используя разложение PA = LU. Точнее, этот шаг использует перестановку строк, а затем прямой и обратный ход для нахождения решения x в зависимости от правостороннего b. В другом варианте, то есть, если матрица является плохообусловленной, мы используем модифицированную версию процедуры DGELSY из LAPACK, которая решает соответствующую задачу наименьших квадратов. Этот выбор может уменьшить точность матрицы промежуточного условия [10].

В [40] Клив Молер (Cleve Moler) анализирует производительность Matlab’а в различных ситуациях, включая решение системы уравнений с помощью оператора обратного слэша. Чтобы измерить производительность вычисления, он подсчитывает число флопсов, измеряя время выполнения в секундах с помощью функций Matlab’а tic и toc и оценивая число операций с плавающей запятой для этого конкретного вычисления. Автор использует матрицу случайных чисел с элементами, полученными из функции нормального распределения и использует функцию randn в Matlab’е. Увеличивая размер матрицы, он наблюдает пик производительности, который соответствует размеру кэша компьютера SPARC-10, который он использует для этого теста. Эта машина имеет кэш в один мегабайт, что соответствует квадратной матрицы порядка --> floor ( sqrt (1. e6 /8)) Название Книга дракона происходит от того, что на обложке книги изображены сражающиеся рыцарь и дракон. (прим. перев.) Точнее, Молер использует определение, которое связывает один мегабайт с 220 байтами, но результат грубо тот же. Пиковая скорость в мегафлопсах получена для матрицы, которая точно укладывается в кэш. Он заявляет, что этот эффект кэша является следствием библиотеки LINPACK. Он подчёркивает, что это одна из главных мотиваций для проекта LAPACK.

Этот документ был написан в 1994: Matlab использует библиотеку LAPACK с 2000 [41]. В [16] Джек Донгарра (Jack Dongarra) собирает различные производительности на этом тесте производительности. Источники по этому вопросу доступны на netlib.org [43].

Общие источники, связанные с улучшением производительности Matlab’а, доступны на [39].

В разделе 5.4.3 мы обсудили установку Scilab’а на Windows. Эта тема обсуждается подробнее на [14], где Аллан Корнэ (Allan Cornet), разработчик из Scilab Consortium, представляет полный процесс установки Scilab 5.2.0 на Windows.

В разделе 5.4.4 мы представили установку двоичной версии ATLAS для Scilab’а на Linux/Ubuntu. Поскольку ATLAS оптимизирован на время сборки, то лучше компилировать собственный ATLAS на той машине, которую планируется использовать. Это гарантирует, что двоичный файл, который мы используем, действительно оптимизирован в соответствии с параметрами текущей машины (например, размер кэша). В [49] Сильвестр Ледрю (Sylvestre Ledru), который является разработчиком из Scilab Consortium и поддерживает пакет Debian Science, предоставляет информацию об установке ATLAS’а на Debian. Этот вопрос представлен более глубоко в [31].

Есть другие ссылки, которые могут помочь пользователям Scilab’а под Linux. В [32] Ледрю описывает процесс установки Scilab 5.1.1 на Linux. В [33] Ледрю обсуждает обновление управления пакетами BLAS и LAPACK в Debian. В [30] Ледрю представляет метод, который позволяет переключаться между различными оптимизированными библиотеками линейной алгебры.

В разделе 5.1.4 мы представили функцию benchfun, которая измеряет производительность указанной функции. В качестве альтернативы мы можем использовать модуль Scibench [6], который предоставляется в ATOMS. Целью проекта Scibench является предоставление инструментов для измерения производительности функции. Более того, модуль предоставляет коллекцию программ измерения производительности для измерения производительности Scilab’а. Внутри модуля Scibench функция scibench_benchfun имеет ту же цель, что и benchfun, которая была представлена в разделе 5.1.4.

5.7 Упражнения Упражнение 5.1 (Метод исключения Гаусса с перестановкой строк ) В разделе 5.1.3 мы представили две функции gausspivotalnaive и gausspivotal, которые включают в себя алгоритм метода исключения Гаусса с перестановкой строк. Используйте функцию benchfun и сравните действительную производительность этих двух функций.

Упражнение 5.2 (Комбинации) Рассмотрим две матрицы чисел типа double размером 1 n x и Y. Допустим, что нам хотелось бы создать функцию, формирующую матрицу c размером 2 m, содержащую все комбинации векторов x и y, с m = n2. То есть, мы хотели бы получить пары [x(1);y(2)], [x(1);y(3)],..., [x(n);y(n)]. Например, рассмотрим следующие матрицы x и y.

Сформируем следующую матрицу c:

• Создайте простую реализацию, формирующую матрицу c.

• Используйте произведение Кронекера.*. и создайте векторизованную функцию для получения матрицы c.

• Используйте выделения матриц, чтобы создать векторизованную функцию для формирования матрицы c.

6 Благодарности Я хочу выразить благодарность Аллану Корнэ (Allan Cornet), Сильвестру Ледрю (Sylvestre Ledru), Бруно Жофрэ (Bruno Jofret) и Бернарду Хугуэнею (Bernard Hugueney) за помощь в подготовке этого документа. Я благодарю Сильвестра Ледрю за информацию, которой он поделился относительно пакета ATLAS на Debian. Бруно Жофрэ ввёл меня в управление памятью в стеке Scilab’а. Я благодарю Аллана Корнэ за информацию, которой он поделился относительно пакетов ATLAS и Intel MKL на Windows. Я благодарю Бенуа Жепфера (Benoit Goepfert) за его комментарии к этому документу. Я благодарю Сержа Стира (Serge Steer) и Майка Пэйджеса (Mike Pages) за их обсуждения гиперматриц.

7 Ответы к упражнениям 7.1 Ответы к разделу Ответ к упражнению 2.1 (Максимальный размер стека) Результат алгоритма, который устанавливает размер стека, зависит от операционной системы. Это результат на Windows-машине:

а это результат на Linux-машине Ответ к упражнению 2.2 (who_user ) Следующий пример результат на Linux-машине.

Пользовательские переменные:

Используется 7 элементов из -->A = ones (100,100);

Пользовательские переменные:

Используется 10009 элементов из На самом деле могут быть иные переменные, определённые пользователем, которые могут быть распечатаны функцией who_user. Например, я установил модуль ATOMS uncprb, и вот что я получаю при запуске:

Пользовательские переменные:

Используется 217 элементов из Это из-за того, что переменная uncprblib содержит библиотеку, связанную с этим конкретным модулем.

Ответ к упражнению 2.3 (whos ) Следующий пример представляет вывод функции whos, которая распечатывает имя, тип, размер и байты, требуемые всеми переменными в текущей среде.

7.2 Ответы к разделу Ответ к упражнению 3.1 (Поиск файлов) Следующая функция searchSciFilesInDir ищет эти файлы в заданной директории.

function filematrix = s ea r c hS c iF i l es I nD i r ( directory, funname ) В нашем примере мы просто распечатываем имя файла. Следующая функция mydisplay использует функцию mprintf распечатывает имя файла в консоли. Для того, чтобы напечатать короткое сообщение, мы убираем имя директории из отображаемой строки. Для того, чтобы выделить название директории из имени файла, мы используем функцию fileparts.

function mydisplay ( filename ) [ path, fname, extension ]= fileparts ( filename ) Далее мы используем функцию searchSciFilesInDir для распечатки файлов-сценариев Scilab из директории Scilab’а, содержащую макросы, связанные с многочленами. Переменная SCI содержит название директории, в которой находится директория Scilab’а. Для того, чтобы определить абсолютное имя файла, содержащее имя директории, содержащей макросы, мы используем функцию fullfile, которая собирает свои входные аргументы в единую строку, отделяя директории разделителем, соответствующим текущей операционной системе (слеш / под Linux и обратный слеш \ под Windows).

--> directory = fullfile ( SCI, " modules "," polynomials "," macros " ) / home / username / scilab -5.2.2/ share / scilab / modules / polynomials / macros --> filematrix = searchSciFiles ( directory, mydisplay );

Ответ к упражнению 3.2 (Запрос типизированных списков) Мы уже видели, что функция definedfields возвращает целые числа с плавающей запятой, связанные с расположением полей в структуре данных. Это не совсем то, что нам здесь нужно, но легко построить нашу собственную функцию на этом строительном блоке. Следующая функция isfielddef принимает типизированный список tl и строку fieldname в качестве входных аргументов и выдаёт логическую переменную bool, которая равна истине, если поле определено, и лжи, если нет. Сначала мы вычисляем ifield, которая является индексом поля fieldname. Чтобы это сделать, мы ищем строку fieldname в полном списке полей, определённом в tl(1) и используем find для поиска требуемого индекса. Затем мы используем функцию definedfields для получения матрицы определённых индексов df. Затем мы ищем индекс ifield в матрице df. Если поиск удался, то переменная k не будет пустой, что значит, что поле определено. Если поиск не удался, то переменная k будет пустой, то означает, что поле не определено.

function bool = isfielddef ( tl, fieldname ) ifield = find ( tl (1)== fieldname ) Несмотря на то, что программа довольно абстрактна, она остаётся простой и эффективной. Её главное преимущество состоит в том, чтобы показать как типизированные списки могут вести к очень динамичным структурам данных 7.3 Ответы к разделу Ответ к упражнению 5.1 (Метод исключения Гаусса с перестановкой строк ) Мы используем следующий файл-сценарий, который создаёт матрицу размером 100 100 и использует её для сравнения производительности функций gausspivotalnaive и gausspivotal.

benchfun ( " naive ", gausspivotalnaive, list (A, b ),1,10);

benchfun ( " fast ", gausspivotal, list (A, b ),1,10);

Этот файл-сценарий производит следующий вывод:

naive : 10 iterations, mean =1.541300, min =1.482000, max =2. fast : 10 iterations, mean =0.027000, min =0.010000, max =0. В этом случае для этого размера матрицы среднее улучшение производительности равно 1,5413/0,027 = 57,08. Фактически, оно могло бы быть больше, при условии, что мы используем достаточно большие матрицы. Для n = 200 мы наблюдали отношение производительностей больше 100.

Ответ к упражнению 5.2 (Комбинации) Мы рассматриваем два вектора x и y, с количеством элементов n. Целью этого упражнения является создание функции, способной генерировать матрицу c размером 2 m, содержащую все комбинации векторов x и y, с количеством элементов m = n2.

Наша первая идея заключается в использовании двух вложенных циклов: эта идея реализована в следующей функции. Первый цикл по ix перебирает элементы в x, в то время, как цикл по iy перебирает элементы в y. Алгоритм устанавливает начальное значение k=1. Каждый раз, когда мы создаём новую комбинацию, мы сохраняем её в k-том столбце матрицы c, а затем мы увеличиваем k.

Показанная функция работает, но она медленная, поскольку требуется выполнить n2 циклов. Следовательно, целью является удалить эти два вложенных цикла и сформировать комбинации с помощью векторизованных инструкций.

Нашей второй идеей является использование произведения Кронекера для формирования всех комбинаций одной-единственной инструкцией. Следующий пример показывает основную идею формирования всех комбинаций векторов [10 11 12] и [13 14 15].

Следующая реализация является прямым обобщением предыдущего примера.



Pages:     | 1 | 2 || 4 |


Похожие работы:

«Министерство образования Российской Федерации Примерная программа по дисциплине ФАРМАЦЕВТИЧЕСКАЯ ТЕХНОЛОГИЯ по специальности 040500 - Фармация Москва, 2002 Министерство образования Российской Федерации Составлена в соответствии с Государственными образовательными с т а н д а р т а м и по соответствующим специальностям высшего профессионального медицинского и фармацевтического образования Примерная программа по дисциплине ФАРМАЦЕВТИЧЕСКАЯ ТЕХНОЛОГИЯ по специальности 040500 Фармация Москва,...»

«УТВЕРЖДЕНО: Директор Фонда Наше будущее /Н.И. Зверева/ __2011 г. ПОЛОЖЕНИЕ О ВСЕРОССИЙКОМ КОНКУРСЕ ПРОЕКТОВ СОЦИАЛЬНЫЙ ПРЕДПРИНИМАТЕЛЬ 2011 (далее – Положение) Настоящее Положение определяет порядок организации и проведения Всероссийского конкурса проектов Социальный предприниматель 2011 (далее по тексту Конкурс). Общие положения I. Всероссийский конкурс проектов Социальный предприниматель 2011 проводится Фондом региональных социальных программ Наше будущее (далее – Фонд), учрежденным Вагитом...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ: Ректор ФГБОУ ВПО КрасГАУ Председатель приемной комиссии _ Н.В. Цугленок “”201 г. ПРОГРАММА ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ ПО СПЕЦИАЛЬНОЙ ДИСЦИПЛИНЕ для поступающих на обучение по программам подготовки научно-педагогических кадров в аспирантуре Институт Землеустройства, кадастров и...»

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Экономический факультет Кафедра теоретической и институциональной экономики Серия ИНСТИТУЦИОНАЛЬНАЯ ЭКОНОМИКА П.С. Лемещенко ИНСТИТУЦИОНАЛЬНАЯ ЭКОНОМИКА Учебная программа для студентов экономических специальностей Минск 2008 2 Цель курса состоит в том, чтобы раскрыть глубокую гамму инструментов, методов и категорий экономической науки, выделив в качестве самостоятельного блока институциональный срез общества и его влияние на экономику. Дефект знания...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ У Ч Е Б Н О -М Е Т О Д И Ч Е С К И Й КОМПЛЕКС по дисциплине Б.2.Б.7 Генетика и биометрия (индекс и наименование дисциплины) Код и направление подготовки 111100.62 – Зоотехния Профиль Технология производства продуктов подготовки животноводства Квалификация Бакалавр (степень) выпускника Факультет...»

«Муниципальное общеобразовательное учреждение Городская основная общеобразовательная школа Калязинского района Тверской области Основная образовательная программа начального общего образования г. Калязин, 2011 год Образовательная программа начальной школы 2012 год МОУ Городская основная общеобразовательная школа г. Калязин Содержание ПАСПОРТ ПРОГРАММЫ I. 4 ИНФОРМАЦИОННАЯ КАРТА II. 7 ЦЕЛЕВОЙ РАЗДЕЛ III. Пояснительная записка 3.1. Планируемые результаты освоения обучающимися основной...»

«Государственное образовательное учреждение высшего профессионального образования Липецкий государственный технический университет Инженерно-строительный факультет УТВЕРЖДАЮ Декан ИСФ Бабкин В.И. _ 2011 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ Основы архитектуры и строительных конструкций 270800.62 Строительство Направление подготовки Профиль подготовки Проектирование зданий Квалификация (степень) выпускника бакалавр Нормативный срок обучения 4 года Форма обучения очная г. Липецк – 2011 г. 1. Цели и...»

«110 ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА 2011. Вып. 1 ФИЛОСОФИЯ. ПСИХОЛОГИЯ. ПЕДАГОГИКА История науки УДК 159.938 Н.И. Леонов ИНСТИТУЦИАЛИЗАЦИЯ КОНФЛИКТОЛОГИИ В НАУЧНО-ОБРАЗОВАТЕЛЬНОМ ПРОСТРАНСТВЕ Рассматривается история становления и развития конфликтологии в Удмуртской Республике. Отмечается, что, институциализируясь, конфликтология была востребована сначала как практическая дисциплина, затем приобрела статус научного направления в научно-образовательном пространстве Удмуртии, России, ближнего и...»

«1. ОБЩИЕ ПОЛОЖЕНИЯ 1. Настоящие Правила приема на обучение по программам подготовки научно-педагогических кадров в аспирантуре (далее – Правила приема) регламентируют прием граждан Российской Федерации, иностранных граждан и лиц без гражданства (далее – граждане, лица, поступающие) в федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Пермский государственный национальный исследовательский университет1 (далее – ПГНИУ, Университет) на обучение...»

«ТАВРИЧЕСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ имени В.И.ВЕРНАДСКОГО Утверждаю Председатель Приемной комиссии (подпись) _ 2014 года ПРОГРАММА вступительного испытания в аспирантуру по специальной дисциплине по направлению подготовки 44.06.01 - Образование и педагогические науки профиль - Теория и методика профессионального образования профиль – Теория и методика обучения и воспитания (математика) профиль – Теория и методика обучения и воспитания (информатика) Утверждено на заседании приёмной комиссии...»

«ПРЕДИСЛОВИЕ Финансы — это наука о принятии финансовых решений. Люди и компании прини мают финансовые решения каждый день, и эти решения должны быть разумными. Эта книга научит читателей принимать правильные теоретические и практические ре шения, а также представлять их с помощью Excel. Обучение финансам на основе Excel преследует две цели — изложить важную теоре тическую и практическую тему (финансы) и показать, как провести финансовый анализ с помощью наиболее распространенных инструментов (в...»

«1 Выпуск № 6 /2014 СОДЕРЖАНИЕ НОМЕРА СОДЕРЖАНИЕ НОМЕРА ОДЕРЖАНИЕ НОМЕРА КОЛОНКА ГЛАВНОГО РЕДАКТОРА.. 3 ДНЕВНИК СОБЫТИЙ:.. 4-14 ВСЕРОССИЙСКИЙ СЪЕЗД ФАРМРАБОТНИКОВ Резолюция Съезда.. 4-6 ОТКЛИКИ НА СЪЕЗД В СМИ.. 7-11 Всеобщий сбор ОБРАЗОВАТЕЛЬНЫЕ ПРОГРАММЫ ААУ Тематические конференции.. 12-14 ААУ СОЮЗФАРМА ИНФОРМИРУЕТ.. 15-23 XX Российский Фармацевтический Форум в Санкт-Петербурге.. 15- Конференция газеты The Moscow Times: Локализация производства в фармацевтической отрасли.. 17- С...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра Бухгалтерского учета и финансов УТВЕРЖДАЮ Декан экономического факультета В.В.Московцев 2011 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) Бухгалтерский учет в торговле (продвинутый курс) Направление подготовки: 0800100.68 Экономика учет, анализ и аудит в Профиль подготовки: Бухгалтерский коммерческих организациях Квалификация...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТУРИЗМА И СЕРВИСА Лист 1 из 35 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТУРИЗМА И СЕРВИСА Лист 2 из 35 Термины, обозначения и сокращения В Тематическом плане комплектования единого библиотечного фонда научно-технической библиотеки ФГБОУ ВПО РГУТиС...»

«Пояснительная записка Рабочая программа курса географии 9 класса разработана на основе: Федерального компонента государственного стандарта общего образования, утвержденного Приказом Минобразования РФ от 05.03.2004 г. №1089. Рабочей программы по предметной линии учебников СФЕРЫ 5-9 классы. – М.: Просвещение, 2011; Требований к оснащению общеобразовательного процесса в соответствии с содержательным наполнением учебных предметов Федерального компонента государственного образовательного стандарта...»

«МИНСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ УТВЕРЖДАЮ Ректор Минского института управления Н.В. Суша (подпись) (дата утверждения) Регистрационный № УД-/р. ОСОБЕННОСТИ РАССМОТРЕНИЯ ХОЗЯЙСТВЕННЫХ СПОРОВ В СФЕРЕ ПРЕДПРИНИМАТЕЛЬСТВА Учебная программа для специальности: 1 24 00 01 – Правоведение Факультет правоведения Кафедра гражданского и трудового права Курс – 5 Семестр – 9 Лекции – 18 часа Экзамен – нет Практические (семинарские) занятия – 16 часов Зачет – 9 семестр Лабораторные занятия – нет Всего аудиторных...»

«ПРАВИТЕЛЬСТВО ИВАНОВСКОЙ ОБЛАСТИ ПОСТАН О В ЛЕНИЕ от 30.12.2013 № 574-п г. Иваново Об утверждении Территориальной программы государственных гарантий бесплатного оказания гражданам медицинской помощи на территории Ивановской области на 2014 год и на плановый период 2015 и 2016 годов В соответствии с федеральными законами от 21.11.2011 № 323-ФЗ Об основах охраны здоровья граждан в Российской Федерации, от 29.11.2010 № 326-ФЗ Об обязательном медицинском страховании в Российской Федерации,...»

«Северо-Кавказский федеральный округ СТАВРОПОЛЬСКИЙ КРАЙ ПАСПОРТ КУЛЬТУРНОЙ ЖИЗНИ за 2011 год 2012 год СОДЕРЖАНИЕ Общая характеристика территории 2 Общеэкономические характеристики территории 2 Характеристика сети культурных учреждений 3 Театрально-концертные организации 6 Изобразительное искусство 15 Творческие союзы 16 Народное творчество и досуговая деятельность 23 Библиотечное дело 26 34 Музейное дело Недвижимые памятники истории и культуры Кинематография Учебные заведения культуры Поддержка...»

«Белорусский государственный университет УТВЕРЖДАЮ Проректор по учебной работе Белорусского государственного университета А.Л. Толстик (дата утверждения) Регистрационный № УД-/баз. Программа дополнительного вступительного экзамена в магистратуру по специальности 1-31 80 06 ХИМИЯ 2013 г Составители: Паньков Владимир Васильевич, заведующий кафедрой электрохимии, доктор химических наук, профессор; Блохин Андрей Викторович, профессор кафедры физической химии, доктор химических наук, профессор;...»

«Глобальный тропический циклогенез и поля поверхностной температуры океана: проблемы спутникового мониторинга Е.А. Шарков, И.В. Покровская Институт космических исследований РАН 117997 Москва, Профсоюзная, 84/32 E-mail: [email protected] На основе анализа результатов дистанционных и гидрометеорологических наблюдений за 1999–2003 гг. показано, что основной характерной структурной особенностью циклогенеза первичных и развитых (тропических циклонов) форм тропических возмущений, возникших в...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.