78004

Исследовании метода Монте-Карло для решения СЛАУ и рассмотрении его параллельной реализации для архитектуры CUDA

Дипломная

Коммуникация, связь, радиоэлектроника и цифровые приборы

Рассматриваются различные подходы к параллельной реализации метода. Предлагается параллельная версия метода для архитектуры CUD и проводится тестирование и исследование ее эффективности при решении СЛАУ различных размерностей.

Русский

2015-02-06

1.15 MB

41 чел.

Аннотация

В работе реализуется параллельная версия метода Монте-Карло для решения разреженных СЛАУ большой размерности на графическом процессоре. Рассматриваются различные подходы к параллельной реализации метода. Предлагается параллельная версия метода для архитектуры CUDA и проводится тестирование и исследование ее эффективности при решении СЛАУ различных размерностей.


Реферат

Расчетно-пояснительная записка к дипломному проекту «Параллельная реализация метода Монте-Карло» содержит 105 страницу машинописного текста, 23 рисунка, 15  таблиц.

В расчетно-пояснительной записке приведен обзор метода Монте-Карло для решения СЛАУ. Предложена и реализована параллельная версия метода для архитектуры CUDA. Произведено исследование метода.


Оглавление

1. Введение 7

2. Конструкторская часть. 9

2.1 Обзор численных методов решения систем линейных алгебраических уравнений (СЛАУ). 9

2.2 Прямые методы решения СЛАУ 10

2.2.1 Метод Гаусса 10

2.2.2 Метод LU–разложения 13

2.2.3 Метод Холецкого (метод квадратного корня) 15

2.3 Итерационные методы решения СЛАУ 16

2.3.1 Метод простой итерации (метод Якоби) 16

2.3.2 Метод Зейделя 17

2.3.3 Метод релаксации 18

2.3.4 Метод сопряженных градиентов 20

2.3.5 Метод бисопряженных градиентов 21

2.3.6 Метод GMRES 22

2.4 Корректность постановки задачи и понятие обусловленности 23

2.5 Экспериментальное исследование устойчивости решения 25

2.6 Вычислительные затраты 26

2.7 Обзор метода Монте-Карло 27

2.7.1 Идея метода 27

2.7.2 Случайные числа 29

2.7.3 Описание метода 31

2.8 Разработка параллельной реализации метода Монте-Карло для решения СЛАУ для архитектуры CUDA 35

2.8.1 Подход «мастер-рабочий» 36

2.8.2 Метод с перешагиванием 36

2.8.3 Разделение последовательностей 37

2.8.4 Параметризация 38

2.8.5 Выбор подхода для параллельной реализации 38

2.8.6 Параллельная реализация метода Монте-Карло 40

3. Технологическая часть. Разработка программного обеспечения реализующего метод Монте-Карло для решения СЛАУ 45

3.1 Обзор используемых технологий и программных платформ 45

3.1.1 Технология NVIDIA CUDA 45

3.1.2 Библиотека CURAND 57

3.1.3 Библиотека CUSP 59

4. Исследовательская часть. Тестирование параллельной реализации метода Монте-Карло и анализ результатов. 61

4.1 Постановка эксперимента 61

4.1.1 Обзор использованных матриц 61

4.1.2 Конфигурация использованного оборудования 64

4.1.3 Методика проведения экспериментов 64

4.2 Результаты эксперимента 66

4.3 Выводы 68

5. Технико-экономическое обоснование эффективности НИОКР 70

5.1 Введение 70

5.2 Расчет трудоемкости выполнения НИОКР 70

5.3 Расчет затрат на выполнение НИОКР 74

5.3.1 Материальные затраты (МЗ) 74

5.3.2 Прочие затраты (ПЗ) 75

5.3.3 Фонд заработной платы (ФЗ) 76

5.3.4 Амортизационные отчисления (АО) 76

5.3.5 Отчисления в фонды (ОТЧ) 78

5.3.6 Полная себестоимость работы (С) 79

5.4 Оценка технического уровня НИОКР 79

5.5 Выводы 80

6. Промышленная экология и безопасность 81

6.1 Введение 81

6.2 Анализ основных факторов воздействия среды на оператора ПК 81

6.3 Критерии проектирования освещения вычислительного центра 83

6.4 Общие положения организации рабочего места 83

6.5 Требования к персональным электронно-вычислительным машинам 84

6.6 Требования к микроклимату на рабочих местах, оборудованных ПЭВМ 87

6.7 Обеспечение требований к размещению оборудования 88

6.8 Отделка помещений для работы с ПЭВМ. 90

6.9 Обеспечение электробезопасности. 91

6.10 Обеспечение пожаробезопасности. 92

6.11 Обеспечение допустимого уровня шума 93

6.12 Расчет системы освещения 94

6.13 Выбор источников света 95

6.14 Выбор системы освещения 95

6.15 Выбор осветительных приборов 96

6.16 Размещение осветительных приборов 96

6.17 Выбор освещенности и коэффициента запаса 98

6.18 Расчет осветительной установки 99

6.19 Утилизация ртутных ламп 102

6.20 Выводы 103

7. Заключение 104

8. Литература 105


Введение

Численное решение систем линейных алгебраических уравнений (СЛАУ) – одна из наиболее часто встречающихся задач в научно-технических исследованиях, математической физике (численное решение дифференциальных и интегральных уравнений), экономике, статистике. Поэтому, методам решения линейных алгебраических уравнений в современной вычислительной математике уделяется большое внимание.

Все методы решения СЛАУ делятся на две большие группы – точные (прямые) и итерационные. Характерной особенностью прямых методов является возможность получить решение системы линейных уравнений за конечное число арифметических операций (метод Гауссаметод квадратного корняправило Крамера и т. д.). Использование итерационных методов дает возможность найти приближенное решение системы с заданной степенью точности (метод простой итерации, метод Зейделя, метод последовательной релаксации).

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

Наряду с детерминированными алгоритмами существует группа численных методов, основанных на получение большого  числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи. Данная группа методов получила название методов Монте-Карло и применяется для решения задач в многочисленных областях физики, математики, экономики, оптимизации, теории управления, а также для решения основной задачи линейной алгебры - нахождения решения системы линейных алгебраических уравнений.

Данные методы интересны тем, что как показано в работах Ермакова С.М. и Данилова Д.Л. при большой размерности СЛАУ метод Монте-Карло обладает меньшей трудоемкостью (в статистическом смысле), чем детерминированные методы. Также, большое преимущество перед другими методами дает методу Монте-Карло его естественное свойство параллелизма.

Первая работа, в которой метод Монте-Карло излагался систематически, была опубликована в 1949 году Метрополисом и Уламом. В ней метод применялся для решения линейных интегральных уравнений, описывающих прохождение нейтронов через вещество.

Цели и задачи дипломного проекта. В связи с тем, что метод Монте-Карло обладает естественных параллелизмом, и развитие аппаратной поддержки параллельных вычислений получило существенное развитие в последнее время, то актуальной задачей является изучение параллельной реализации метода. Цель данного дипломного проекта состоит в исследовании метода Монте-Карло для решения СЛАУ и рассмотрении его параллельной реализации для архитектуры CUDA. Необходимо произвести тестирование реализованного алгоритма, исследовать его эффективность для решения разреженных СЛАУ больших размерностей.


Конструкторская часть. 

  1.  
  2.  

Обзор численных методов решения систем линейных алгебраических уравнений (СЛАУ).

Рассмотрим систему линейных алгебраических уравнений (СЛАУ) [1,2]

                          (1)

где .

Будем предполагать, что определитель матрицы отличен от нуля, т.е. решение системы (1) существует.

Методы численного решения системы (1) делятся на две большие группы: прямые методы («точные») и итерационные методы.

Прямыми методами называются методы, позволяющие получить решение системы (1) за конечное число арифметических операций. К этим методам относятся метод Крамера, метод Гаусса, LU-метод и т.д.

Итерационные методы (методы последовательных приближений) состоят в том, что решение системы (1) находится как предел последовательных приближений при , где n номер итерации. При использовании методов итерации обычно задается некоторое малое число 0 и вычисления проводятся до тех пор, пока не будет выполнена оценка . К этим методам относятся метод Зейделя, Якоби, метод верхних релаксаций и т.д. Данные методы хорошо применимы к решению разреженных матриц.

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

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

Прямые методы решения СЛАУ

Метод Гаусса

Запишем систему  Ax=f,   в развернутом виде                                                

                                                                    (2)

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

                    (3)

где

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

                   (4)

Описанная процедура называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при условии, что все , не равны нулю.

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

   .                              (5)

Эта процедура получила название обратный ход метода Гаусса.

Метод Гаусса может быть легко реализован на компьютере. При выполнении вычислений, как правило, не интересуют промежуточные значения матрицы А. Поэтому   численная  реализация  метода  сводится  к  преобразованию элементов массива размерности (m×(m+1)), где m+1 столбец содержит элементы правой части системы.

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

Один из основных недостатков метода Гаусса связан с тем, что при его реализации накапливается вычислительная погрешность. В [1] показано, что для больших систем порядка m число действий умножений и делений близко к .

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

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

Выполняемые в методе Гаусса преобразования прямого хода, приведшие матрицу А системы к треугольному виду позволяют вычислить определитель матрицы

.                       (6)

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

,                            (7)

где Е единичная матрица. Его решение сводится к решению m систем

                         (8)

у вектора  j –я компонента равна единице, а остальные компоненты равны нулю.

Метод LU–разложения

Метод LU-разложения основан на том, что если главные миноры матрицы А отличны от нуля, тогда матрицу А можно представить, причем единственным образом, в виде произведения

А=LU,                          (9)

где L–нижняя треугольная матрица с ненулевыми диагональными элементами и U–верхняя треугольная матрица с единичной диагональю:

             (10)

или

,                    (11)

где

Окончательно запишем

                    (12)

                     (13)

Полагая получим следующие рекуррентные формулы для вычисления элементов матрицы L и U

                    (14)

Если найдены матрицы L и U, то решение исходной системы (1)ID_1 сводится к последовательному решению двух систем уравнений с треугольными матрицами

                       (15)

Метод Холецкого (метод квадратного корня)

   Метод квадратного корня по своему идейному содержанию близок к LU-методу. Основное отличие в том, что он дает упрощение для симметричных матриц.ID_1

Этот метод основан на разложении матрицы А в произведение

                       (16)

где S–верхняя треугольная матрица с положительными элементами на главной диагонали, ST – транспонированная к ней матрица.

Основываясь на выводе, предложенном в [13] получим следующее соотношение для разложения матрицы А:

                   (17)

В частности, при i=j получится

                        (18)

Далее, при i<j получим

                               (19)

По  формулам (18)  и  (19) находятся рекуррентно все ненулевые   элементы матрицы S.

Обратный ход метода квадратного корня состоит в последовательном решении двух систем уравнений с треугольными матрицами.

                     (20)

Решения этих систем находятся по рекуррентным формулам                    (21)

               (22)

   Всего метод квадратного корня при факторизации A=SтS требует примерно операций умножения и деления и m операций извлечения квадратного корня.[1]

Итерационные методы решения СЛАУ

Метод простой итерации (метод Якоби)

Для того чтобы применить метод простой итерации к решению системы линейных алгебраических уравнений (1) с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

                            (23)

Здесь B – квадратная матрица с элементами ,

с – вектор-столбец с элементами .

Вообще говоря, операция приведения системы к виду, удобному для итерации [т.е. к виду (23)], не является простой и требует специальных знаний, а также существенного использования специфики системы. В некоторых случаях в таком преобразовании нет необходимости, так как сама исходная система уже имеет вид (23). Часто систему (1) преобразуют к виду: , где τ– специально выбираемый числовой параметр.

Выберем начальное приближение . Подставляя его в правую часть системы (23) и вычисляя полученное выражение, находим первое приближение:

                      (24)

Продолжая этот процесс далее, получим последовательность приближений, вычисляемых по формуле:

                             (25)

Для рассмотрения вопроса о сходимости метода простой итерации приведем теорему:

Теорема. Пусть выполнено условие

                        (26)

Тогда:

  1.  решение  системы (23) существует и единственно; 
  2.  при произвольном начальном приближении метод простой итерации сходится и справедлива оценка погрешности

                      (27)

Оценим трудоемкость предложенного алгоритма. Анализ расчетных фор- мул показывает, что они включают одну операцию умножения матрицы на вектор и три операции над векторами (сложение, вычитание, умножение на константу). Общее количество операций, выполняемых на одной итерации, составляет [13]:

                      (28)

Метод Зейделя 

Пусть система (1) приведена к виду (23). Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-го приближения к неизвестному  при используют уже найденные (k+1)-е приближения к неизвестным , а не k-е приближения, как в методе Якоби.

На (k+1)-й итерации компоненты приближения   вычисляются по формулам

 

                (29)  

Введем нижнюю и верхнюю треугольную матрицы:

               (30)

Тогда расчетные формулы метода примут компактный вид:

                           (31)

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

Изучим сходимость метода. Для этого рассмотрим теорему.

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

Метод релаксации

Исходная система линейных уравнений (1) приводится к виду:

                                                   (32)

где

 ,  и .

Пусть - начальное приближение системы (32). Подставляя эти значения в систему (32) получим невязки

                                                                                

         (33)

Если одной из неизвестных  дать приращение , то соответствующая невязка уменьшится на величину , а все остальные невязки () увеличатся на величину . Таким образом, чтобы обратить очередную невязку в нуль достаточно величине   дать приращение

                      (34)

Тогда

                            (35)

при                     (36)

Метод релаксации (по-русски: метод ослабления) [3], [4] в его простейшей форме заключается в том, что на каждом шаге обращают в нуль максимальную по модулю невязку путем изменения значения соответствующей компоненты приближения. Процесс заканчивается, когда все невязки последней преобразованной системы будут равны нулю с заданной точностью.

Метод сопряженных градиентов

Рассмотрим систему линейных уравнений (1) с симметричной, положительно определенной матрицей A размера nxn. Основой метода сопряженных градиентов является следующее свойство: решение системы линейных уравнений (1) с симметричной положительно определенной матрицей A эквивалентно решению задачи минимизации функции

                    (37)

в пространстве Rn. В самом деле, функция F(x) достигает своего минимального значения тогда и только тогда, когда ее градиент

                      (38)

обращается в ноль. Таким образом, решение системы (1) можно искать как решение задачи безусловной минимизации (38). 

С целью решения задачи минимизации (38) организуется следующий итерационный процесс.

Подготовительный шаг (s=0) определяется формулами

                      (39)

                     (40)

где  – произвольное начальное приближение,  вычисляется как

                      (41)

 Основные шаги (s=1, 2,..., n-1) определяются формулами

  

               (42)
                     (43)

Здесь  невязка s-го приближения,  находят из условия сопряженности

                      (44)

направлений  и  , а  является решением задачи минимизации функции F по направлению  

                     (45)

Можно показать, что для нахождения точного решения системы линейных уравнений с положительно определенной симметричной матрицей необходимо выполнить не более n итераций, тем самым, сложность алгоритма поиска точного решения имеет порядок O(n3). Однако ввиду ошибок округления данный процесс обычно рассматривают как итерационный, процесс завершается либо при выполнении обычного условия остановки, либо при выполнении условия малости относительной нормы невязки

                      (46)

Общее количество числа операций, выполняемых на одной итерации, составляет [13]:

                      (47)

Метод бисопряженных градиентов

Пусть требуется решить систему уравнений (1). Общая идея метода бисопряженных градиентов для решения линейной системы уравнений (1) заключается в итеративной генерации пары остатков r и , вычисляемых как

                     (48)

                     (49)

где p и векторы направлений:

                    (50)

                    (51)

 и  выбираются таким образом, чтобы выполнялись отношения ортогональности:

для                    (52)

                   (53)

Следует отметить использование матрицы M [21] в качестве матрицы предобусловливания (preconditioner). Использование предобусловливания во многих случаях позволяет на порядки сократить время вычислений. Причина заключается в том, что скорость сходимости итеративных методов зависит от спектральных характеристик матрицы коэффициентов. Соответственно, можно попытаться так преобразовать систему, чтобы она имела те же решения, что и исходная, но при этом имела бы лучшую (относительно метода решения) спектральную характеристику.

Выбор матрицы предобусловливания часто является достаточно сложной творческой задачей, поскольку на настоящий момент неизвестно удобных на практике формальных алгоритмов для такого выбора (хотя существует несколько наиболее распространенных вариантов [22]). Одним из наиболее распространенных является реализация предобусловливателя на основе алгоритма неполного LU-разложения [22]. Подробное описание метода приведено в [21, 23].

Метод GMRES

Метод GMRES [20, 21] был предложен для решения несимметричных СЛАУ и основан на построении базиса в соответствующем системе подпространстве Крылова Kj(A,r0). Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису.

В несимметричном случае основная сложность заключается в том, что для построения ортогонального базиса не могут быть использованы рекуррентные соотношения с малой глубиной зависимости типа тех, что применяются в методе сопряженных градиентов. Поэтому в GMRES ортонормальный базис {vj} строится на основе следующего соотношения, выражающего полную зависимость всех векторов:

                    (54)

где

В матрично-векторных обозначениях соотношение (54) может быть записано как

                         (55)

где

,

- матрица размерности  в верхней форме Хессенберга.

Особенностью GMRES является то, что с целью экономии памяти выбирается некоторая размерность подпространства Крылова m (причем ), и после того как m базисных векторов построены решение уточняется. Построение очередного вектора vi обычно называют GMRES-итерацией, а m таких итераций с уточнением решения — GMRES-циклом. Один цикл требует m +1 матрично-векторное умножение. Подробное описание GMRES приведено в [20, 21].

Корректность постановки задачи и понятие обусловленности

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

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

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

Известно, что решение задачи (1) существует тогда и только тогда, когда . В этом случае можно определить обратную матрицу и решение записать в виде .

Исследование устойчивости задачи (1) сводится к исследованию зависимости ее решения от правых частей и элементов матрицы А. Для того чтобы можно было говорить о непрерывной зависимости вектора решений от некоторых параметров, необходимо на множестве - мерных векторов принадлежащих линейному пространству H, ввести метрику.

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

при р=1, ,

при , ,

при , .

Подчиненные нормы матриц определяемые как

,                       (56)

соответственно запишутся в следующем виде:

, , .                (57)

Обычно рассматривают два вида устойчивости решения системы (1):первый  по правым частям, второй  по коэффициентам системы(1) и по правым частям..

Наряду с исходной системой (1) рассмотрим систему с «возмущенными» правыми частями

,                        (58)

где возмущенная правая часть системы,

- возмущенное решение.

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

,                       (59)

где число обусловленности матрицы А (в современной литературе это число обозначают как ). Если число обусловленности велико (  ), то говорят, что матрица А плохо обусловлена. В этом случае малые возмущения правых частей системы (1), вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления существенно влияют на решение системы. Грубо говоря если погрешность правых частей , то погрешность решения будет . Более подробно о свойствах числа обусловленности и оценке его величины можно прочитать в [3].

Если возмущение внесено в матрицу А, то для относительных возмущений решения запишем

.                     (60)    

Экспериментальное исследование устойчивости решения

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

Пусть получено приближенное решение системы (1) . Вычислим невязку уравнения . Если велико, то можно искать вектор-поправку такой, что точное решение системы . Следовательно

,                      (61)

отсюда

.                        (62)

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

Вычислительные затраты

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

Учитывая, что операция сложения выполняется намного быстрее, чем операция умножения и деления, обычно ограничиваются подсчетом последних.

Для решения СЛАУ методом Гаусса без выбора главного элемента  требуется умножений и делений, решение СЛАУ методом квадратного корня требует и m операций извлечения корней. Метод вращения предполагает вчетверо больше операций умножения, чем в методе Гаусса. При больших значениях размерности m, можно сказать, что вычислительные затраты на операции умножения и деления в методе Гаусса составляют величину , в методе квадратных корней , в методе вращений .

Общее количество операций, выполняемых на одной итерации метода Якоби, составляет [13]: . Для метода сопряженных градиентов это количество составляет: . Один цикл метода GMRES требует m +1 операций матрично-векторного умножения.  

Обзор метода Монте-Карло

Идея метода

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

                        (63)

причем в случае конечного числа операций процесс обрывается на некотором шаге.

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

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

                       (64)

где P – соответствующая вероятность.

Выбор величины  обусловливается конкретными особенностями задачи. Например, часто искомую величину  трактуют как вероятность некоторого случайного события (или, более общо, как математическое ожидание некоторой случайной величины). Тогда частоту  появления события при n соответствующих случайных испытаниях (или соответственно эмпирическое среднее значений случайной величины) в широких предположениях можно рассматривать как вероятностную оценку искомой величины. Возможны также и другие варианты. Следует заметить, что в этих случаях вычислительный процесс является недетерминированным, так как он определяется итогами случайных испытаний.

Способы решения задач, использующие случайные величины, получили общее название метода Монте-Карло, Более точно под методом Монте-Карло [6], [7], [8], [9] понимается совокупность приемов, позволяющих получать решения математических или физических задач при помощи многократных случайных испытаний. Оценки искомой величины выводятся статистическим путем и носят вероятностный характер. На практике случайные испытания заменяются результатами некоторых вычислений, производимых над случайными числами.

Случайные числа

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

Величина называется случайной, если она принимает те или иные значения в зависимости от появления или не появления некоторого случайного события. Случайная величина X задается законом распределения

                     (65)

где  - любое действительное число и  известная функция (функция распределения). Существует несколько основных и наиболее значимых законов распределения: равномерный и нормальный законы. Рассмотрим последовательность случайных чисел равномерно распределенных на отрезке (a, b). Для такой последовательности имеет место соотношение

,                       (66)

где – число элементов последовательности , принадлежащих промежутку (a, b).

Следует заметить, что, имея случайную последовательность , равномерно распределенную на отрезке [0, 1], можно построить случайную последовательность  с заданным законом распределения Ф(у).

Для решения задач методом Монте-Карло обычно требуется весьма большое количество случайных чисел. Эти числа практически наиболее удобно получаются с помощью специальных датчиков случайных чисел, подключаемых к машине. Действие этих датчиков регулируется случайными физическими процессами (например, радиоактивным распадом, шумами в электронных лампах и т. п.) [9].

Так как воспроизводство случайных чисел, отвечающих данной теоретической модели, есть процесс весьма тонкий и сложный, то на практике часто ограничиваются получением, так называемых  псевдослучайных чисел, в основных чертах похожих на соответствующие случайные. Источниками (датчиками) псевдослучайных чисел служат достаточно сложные математические алгоритмы.

При решении СЛАУ больших размерностей методом Монте-Карло требуется создавать n-мерные последовательности, при этом генератор псевдослучайных чисел часто не может создавать достаточно равномерно распределенные последовательности. В таких ситуациях возможно пожертвовать «случайностью» и создавать последовательности с более равномерным покрытием области. Числа, полученные в результате таких действий, называются квазислучайными (КСЧ). В ряде задач (например, в задаче численного интегрирования) применение последовательностей КСЧ обеспечивает существенно лучшую сходимость по сравнению с реализациями метода Монте-Карло, основанными на использовании псевдослучайных чисел (ПСЧ) [14].

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

Рис. 1. Псевдо и квазислучайные точки

Описание метода

Пусть исходная система уравнений записана в виде:

Bx=f                         (67) 

где B квадратная матрица размерности nхn, обладающая диагональным приобладанием,

 x – вектор неизвестных, 

f – вектор значений правой части системы.

Приведем систему (67) к виду:

x=Ax+f                         (68)

Будем полагать, что для системы (2) имеет место соотношение:  

 .                     (69)

От системы (67) к системе (68) можно перейти с помощью следующих преобразований. Пусть для фиксированного i . Если в i-м уравнении системы (1) коэффициент , то делим каждый член этого уравнения на L, в противном случае на L. Обозначим  и      . Полученные числа и будут коэффициентами системы (68) [13].

Сопоставим теперь i-му уравнению этой системы разбиение отрезка [0…1] на n+1 отрезков точками sj, каждая из которых имеет координату, определяемую соотношениями . Положим .

Рассмотрим процесс «случайного блуждания» некоторой частицы, которая в начальный момент находится в точке  i-го разбиения отрезка     [0; 1] (диагональный элемент i-й строки). Воспользуемся возможностью получения случайных чисел, равномерно распределенных на отрезке [0; 1], рассмотрим такое случайное число c. Если оно удовлетворяет соотношению  для точек рассматриваемого i-го разбиения, то считаем, что частица переходит из точки  i-го разбиения в точку  j-го разбиения (на j-ю строку, диагональный элемент).

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

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

Доказано [8, 11, 12], что математическое ожидание случайной величины  равно значению корня  системы уравнений. Осуществим М реализаций случайного блуждания частицы по траектории, начинающейся в точке . Обозначим через Y  сумму значений случайной величины , полученных во всех реализациях, т.е. . Тогда будем иметь приближенное равенство

Более наглядное представление о структуре алгоритма можно получить, если обратиться к блок-схеме метода, представленной на рисунке 2.

Рис.2. Блок-схема метода Монте-Карло

Рассмотрим более подробно создание цепи Маркова. Для этого обратимся к схеме алгоритма создания цепи Маркова представленной в псевдокоде:

Входные данные: root, p, v, offsets, colInd, w;

Результат: y;

целое curEq := root;

целое  vv := 1;

флаг isFound;

while( true )

{

 isFound := false;

создать равномерно распределенное случайное число rNum;

целое j := 0;

while( j < offsets[curEq + 1] – offsets[curEq] )

{

if( rNum  p[offsets[curEq] + j] )

{

vv := vv*v[offsets[curEq] + j];

curEq := colInd[offsets[curEq] + j];

isFound := true;

 выход из цикла;

}

 j := j + 1;

}

if( isFound != true )

{

 y := y + vv*w[curEq];

 выход из цикла;

}

}

Входными данными являются указатели на массивы, содержащие элементы матрицы переходов (p), знаки коэффициентов исходной системы (v), строковые указатели (offsets), столбцовые индексы (colInd), элементы вектора весов (w). Результат записывается в вещественную переменную y.

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

Еще одна особенность метода Монте-Карло состоит в том, что он существенным образом зависит от возможности генератора ПСЧ сгенерировать достаточно много «хороших» последовательностей. Таким образом, выбор качественного генератора псевдослучайных чисел является очень важным моментом при реализации данного метода.

Разработка параллельной реализации метода Монте-Карло для решения СЛАУ для архитектуры CUDA

Одним из хорошо известных преимуществ метода Монте-Карло является высокая эффективность, с которой он может быть распараллелен. Различные процессы (нити) могут создавать независимые случайные блуждания и получать при помощи них свои собственные оценки искомой величины (или корня СЛАУ в рассматриваемом случае). Далее необходимо собрать эти «индивидуальные» оценки для получения конечного результата.

Как уже ранее было замечено, параллельные методы Монте-Карло существенным образом зависят от возможностей генератора ПСЧ. В дополнение к свойствам, которым должен обладать последовательный генератор, должны выполняться также следующие свойства:

  1.  Независимость: числа из различных последовательностей должны быть не коррелированны.
  2.  Масштабируемость: нужно уметь генерировать столько последовательностей, сколько нужно для работы с большим числом потоков.

Рассмотрим некоторые подходы к распараллеливанию метода Монте-Карло [14].

Подход «мастер-рабочий»

Очевидным способом распараллеливания метода Монте-Карло является метод «мастер-рабочий». Поток-мастер, используя генератор, порождает последовательность случайных чисел, и распределяет полученные числа по рабочим потокам.

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

Второй недостаток заключается в том, что метод «мастер-рабочий» плохо масштабируется на произвольное число потоков. Сложно сбалансировать скорость работы генератора случайных чисел в потоке-мастере со скоростью обработки этих чисел в потоках-рабочих. Если обработка очередного случайного числа является трудоемкой (по сравнению с его генерацией), то потоки-рабочие не будут справляться с обработкой потока поступающих чисел. В противном случае потоки-рабочие будут простаивать, ожидая, пока мастер сгенерирует очередное случайное число.

Эти недостатки делают данный подход практически неприемлемым, особенно для SIMD архитектуры.

Метод с перешагиванием

Метод с перешагиванием аналогичен циклической схеме распределения данных по потокам. Предположим, что метод Монте-Карло выполняется в p-поточной программе. Каждый поток имеет свою копию одного и того же генератора случайных чисел, порождающего последовательность Xn; при этом i-й поток обрабатывает каждое p-е число последовательности, начиная с Xi:

Xi, Xi+p, Xi+2p,…

На рис. 3 изображены элементы последовательности, генерируемые методом во 2-м потоке 4-х поточной программы

Рис. 3. элементы последовательности, генерируемые методом во 2-м потоке 4-х поточной программы

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

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

Разделение последовательностей

Метод разделения последовательности аналогичен блочной схеме распределения данных между потоками. Пусть T – период используемого генератора случайных чисел, а  – длина последовательности, которую мы хотим обработать. Тогда последовательность длины N разделяется на подпоследовательности равной длины по одной для каждого из p потоков. В этом случае каждый поток работает с непрерывной частью исходной последовательности.

Рис. 4. Разделение последовательности

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

Параметризация

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

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

Выбор подхода для параллельной реализации

Рассмотрим описанные выше подходы с точки зрения их применимости к SIMD архитектуре CUDA. Для этого необходимо обратить внимание на некоторые ограничивающие особенности данной архитектуры. Так ядро, отвечающее за выполнение случайных блужданий, должно содержать как можно меньше инструкций и обращений к регистровой  памяти, так как ресурсы данного типа памяти весьма ограничены в пределах блока.

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

Из-за специфики SIMD архитектуры нет возможности использовать различные генераторы псевдослучайных чисел в различных нитях и блоках. Кроме того рекомендуется чтобы сам генератор обладал как можно меньшим количеством параметров, необходимых для его инициализации и хранения его состояния, потому как данный набор параметров необходимо хранить между различными вызовами генератора. Таким образом, подходы «мастер-рабочий», «параметризация» и «метод с перешагиванием» не подходят по совокупности причин.

Рассмотрим подход «Разделение последовательностей» с точки зрения SIMD архитектуры CUDA. Одним из недостатков данного подхода является сложность вычисления -го члена последовательности как начального элемента в i-м потоке (нити, в терминах архитектуры CUDA). Однако генераторы, предоставляемые библиотекой CURAND, обладают встроенной возможностью определения подпоследовательности, соответствующей конкретной нити.

При использовании библиотеки CURAND в качестве генератора «по умолчанию» используется генератор XORWOW, обладающий периодом 2192 -1. В случае использования данного генератора на каждую подполседовательность приходится 267 случайных чисел  [18]. Данный генератор использует относительно «легковесную» структуру данных для хранения своего состояния, что также является его преимуществом. Таким образом, подход с разделением последовательностей является оптимальным с точки зрения SIMD архитектуры CUDA.

Параллельная реализация метода Монте-Карло

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

Так как метод обладает естественным параллелизмом, то будем осуществлять вычисление каждого корня СЛАУ в соответствующем блоке, внутри блока будем вычислять «индивидуальные» оценки корня СЛАУ. Размерность блока примем равной максимально возможной для данного графического адаптера. Более наглядно структуру программы можно изучить, обратившись к рис. 5.

Анализ матрицы, преобразование матрицы к виду x=Ax+f  , проверка нормы преобразованной матрицы

Расчет матрицы перехода и вектора весов

Запуск ядра для расчета корней СЛАУ

Отправка матрицы переходов, вектора весов на графический адаптер

Чтение матрицы коэффициентов СЛАУ из формата Matrix Market

Запись результатов в файл

Рис. 5. Структура программы

На вход программа получает имя файла с разреженной матрицей, хранящейся в формате Matrix Market. Далее при помощи библиотеки CUSP производится считывание файла во внутренний формат программы – разреженный строчный формат, удобный для обработки методом Монте-Карло.

Рассмотрим блок-схему ядра CUDA, реализующего оценку конкретного корня СЛАУ, представленную на рис. 6. На вход ядро получает указатели на массивы описывающие матрицу переходов и знаков в строчном разреженном формате, а также вектор весов, зерно для генератора случайных чисел и указатель на массив результатов. Внутри ядра каждая нить определяет свой глобальный и локальный индексы и в соответствии с ними происходит инициализация генератора случайных чисел, например, так:

 curandState localState;

curand_init(seed, gid, 0, &localState);

где gid – глобальный индекс нити, seed – зерно генератора случайных чисел, localState – структура, хранящая состояние генератора. В данной реализации метода Монте-Карло в качестве генератора случайных чисел использовался генератор XORWOW, его подробное описание можно найти в [17].

Далее выполняется процедура барьерной синхронизации нитей внутри одного блока, и они приступают к созданию цепей Маркова для оценки корня СЛАУ. Так как каждая нить совершает оценок корня, то необходимо просуммировать результаты полученные отдельными нитями. Данная процедура также выполняется параллельно при помощи алгоритма свертки массива, представленного на рис. 7.

Рис. 6. Блок-схема ядра

Рис. 7. Свертка массива

Технологическая часть. Разработка программного обеспечения реализующего метод Монте-Карло для решения СЛАУ

  1.  

Обзор используемых технологий и программных платформ

Технология NVIDIA CUDA

Рассмотрим  некоторые существенные отличия между областями и особенностями применений центрального процессора и видеокарты.

Центральный процессор (CPU) изначально приспособлен для решения задач общего плана и работает с произвольно адресуемой памятью. Программы могут обращаться напрямую к любым ячейкам линейной и однородной памяти.

Для графического адаптера (GPU) это не так. В архитектуре CUDA имеется 6 различных видов памяти. Читать можно из любой ячейки, доступной физически, но вот записывать – не во все ячейки. Причина заключается в том, что графический адаптер в общем случае представляет собой специфическое устройство, предназначенное для конкретных целей. Это ограничение введено ради увеличения скорости работы определенных алгоритмов и снижения стоимости оборудования.

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

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

На GPU (здесь и далее подразумевается видеокарты GF восьмой серии и выше) кэш-память тоже есть, и она тоже важна, но этот механизм не такой мощный, как на CPU. Во-первых, кэшируется не все типы памяти, а во-вторых, кэш-память работает только на чтение.

На GPU медленные обращения к памяти скрывают, используя параллельные вычисления. Пока одни задачи ждут данных, работают другие, готовые к вычислениям. Это один из основных принципов CUDA, позволяющих сильно поднять производительность системы в целом.

Вычислительная архитектура CUDA основана на концепции одна команда на множество данных (Single Instruction Multiple Data, SIMD) и понятии мультипроцессора [15]. Концепция SIMD подразумевает, что одна инструкция позволяет одновременно обработать множество данных.

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

Для дальнейшего рассмотрения архитектуры CUDA необходимо ввести такие понятия как хост (host) и устройство (device). Устройством (device) является  видеоадаптер, поддерживающий драйвер CUDA, или другое специализированное устройство, предназначенное для исполнения программ, использующих CUDA (такое, например, как NVIDIA Tesla). Рассмотрим GPU только как логическое устройство, избегая конкретных деталей реализации.

Хост (host) это программа в обычной оперативной памяти компьютера, использующая CPU и выполняющая управляющие функции по работе с устройством. Фактически, та часть программы, которая работает на CPU — это хост, а видеокарта — устройство. Логически устройство можно представить как набор мультипроцессоров (рис.8) плюс драйвер CUDA.


Рис. 8. Устройство

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

Особенностью архитектуры CUDA является блочно-сеточная организация, необычная для многопоточных приложений (рис. 9). При этом драйвер CUDA самостоятельно распределяет ресурсы устройства между потоками.


Рис. 9. Организация потоков

На рис. 9. изображено ядро. Все потоки, выполняющие это ядро, объединяются в блоки, а блоки, в свою очередь, объединяются в сетку.

Как видно на рис. 9, для идентификации потоков используются двухмерные индексы. Разработчики CUDA предоставили возможность работать с трехмерными, двухмерными или простыми (одномерными) индексами, в зависимости от того, как удобно программисту. В общем случае индексы представляют собой трехмерные векторы. Для каждого потока будут известны: индекс потока внутри блока threadIdx и индекс блока внутри сетки blockIdx. При запуске все потоки будут отличаться только этими индексами. Фактически, именно через эти индексы программист осуществляет управление, определяя, какая именно часть его данных обрабатывается в каждом потоке.

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

Блок задач (потоков) выполняется на мультипроцессоре частями, или пулами, называемыми warp. Размер warp на текущий момент в большинстве видеокарт с поддержкой CUDA равен 32 потокам. Задачи внутри пула warp исполняются в SIMD стиле, т.е. во всех потоках внутри warp одновременно может выполняться только одна инструкция.

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

Сразу же возникает вопрос: если в один и тот же момент времени все потоки внутри warp исполняют одну и ту же инструкцию, то как быть с ветвлениями? Ведь если в коде программы встречается ветвление, то инструкции будут уже разные. Здесь применяется стандартное для SIMD программирования решение (рис 10).

Пусть имеется следующий код:

A;

if(cond) B;

else  C;

D;

В случае SISD (Single Instruction Single Data) мы выполняем оператор A, проверяем условие, затем выполняем операторы B и D (если условие истинно).

Пусть есть 10 потоков, исполняющихся в стиле SIMD. Во всех 10 потоках выполняется оператор A, затем проверяем условие cond и оказывается, что в 9 из 10 потоках оно истинно, а в одном потоке — ложно.


Рис. 10. Организация ветвления в SIMD

Понятно, что мы не можем запустить 9 потоков для выполнения оператора B, а один оставшийся — для выполнения оператора C, потому что одновременно во всех потоках может исполняться только одна инструкция. В этом случае нужно поступить так: сначала «убиваем» отколовшийся поток так, чтобы он не портил ничьи данные, и выполняем 9 оставшихся потоков. Затем «убиваем» 9 потоков, выполнивших оператор B, и проходим один поток с оператором C. После этого потоки опять объединяются и выполняют оператор D все одновременно.

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

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

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

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

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

 

Рис. 11. Иерархия памяти в архитектуре CUDA

В архитектуре CUDA выделяют шесть видов памяти [16, 17] (рис. 11). Это регистры, локальная, глобальная, разделяемая, константная и текстурная память. Такое обилие обусловлено спецификой видеокарты и первичным ее предназначением, а также стремлением разработчиков сделать систему как можно дешевле, жертвуя в различных случаях либо универсальностью, либо скоростью.

По возможности компилятор старается размещать все локальные переменные функций в регистрах. Доступ к таким переменным осуществляется с максимальной скоростью. В текущей архитектуре на один мультипроцессор доступно 8192 32-разрядных регистра. Для того чтобы определить, сколько доступно регистров одному потоку, надо разделить это число (8192) на размер блока (количество потоков в нем). При обычном разделении в 64 потока на блок получается всего 128 регистров (существуют некие объективные критерии, но 64 подходит в среднем для многих задач).

Если учесть, что на одном мультипроцессоре может исполняться несколько блоков, то для большей эффективности надо стараться занимать меньше 64 или даже меньше 32 регистров. Тогда теоретически может быть запущено 4 блока на одном мультипроцессоре. Однако здесь еще следует учитывать объем разделяемой памяти, занимаемой потоками, так как если один блок занимает всю разделяемую память, два таких блока не могут выполняться на мультипроцессоре одновременно

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

В документации CUDA [17] в качестве одного из основных достижений технологии приводится возможность произвольной адресации глобальной памяти. То есть можно читать из любой ячейки памяти, и писать можно тоже в произвольную ячейку (в общем случае  на GPU это обычно не так). Однако за универсальность в данном случае приходится расплачиваться скоростью. Глобальная память не кэшируется. Она работает очень медленно, количество обращений к глобальной памяти следует в любом случае минимизировать.
Глобальная память необходима в основном для сохранения результатов работы программы перед отправкой их на хост (в обычную оперативную память графического адаптера). Причина этого в том, что глобальная память — единственный вид памяти, куда можно что-то записывать.

Переменные, объявленные с квалификатором __global__, размещаются в глобальной памяти. Глобальную память также можно выделить динамически, вызвав функцию cudaMalloc(void* mem, int size) на хосте. Из устройства эту функцию вызывать нельзя. Отсюда следует, что распределением памяти должна заниматься программа-хост, работающая на CPU. Данные с хоста можно отправлять в устройство вызовом функции cudaMemcpy:

cudaMemcpy(void* gpu_mem, void* cpu_mem, int size, cudaMemcpyHostToDevice);

Точно таким же образом можно проделать и обратную процедуру:

cudaMemcpy(void* cpu_mem, void* gpu_mem, int size, cudaMemcpyDeviceToHost);

Этот вызов тоже осуществляется с хоста.

Разделяемая память — это некэшируемая, но быстрая память. Ее следует использовать как управляемый кэш. На один мультипроцессор доступно всего порядка 16 Кб разделяемой памяти. Разделив это число на количество задач в блоке, можно получить максимальное количество разделяемой памяти, доступной на один поток (если планируется использовать ее независимо во всех потоках). Отличительной чертой разделяемой памяти является то, что она адресуется одинаково для всех задач внутри блока (рис. 5). Отсюда следует, что ее можно использовать для обмена данными между потоками только одного блока.

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

__shared__ float  mem_shared[N_THREADS];

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

float x = mem_shared[threadIdx.x];

Где threadIdx.x — индекс x потока внутри блока.

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

Так как для константной памяти используется кэш, доступ к ней в общем случае довольно быстрый. Единственный, но очень большой недостаток константной памяти заключается в том, что ее размер составляет  всего 64 Kб (на все устройство). Из этого следует, что в константной памяти имеет смысл хранить лишь небольшое количество часто используемых данных.

Текстурная память кэшируется (рис. 8). Для каждого мультипроцессора имеется только один кэш, а значит, этот кэш общий для всех задач внутри блока. Название текстурной памяти и функциональность унаследованы от понятий «текстура» и «текстурирование». Текстурирование — это процесс наложения текстуры (картинки) на полигон в процессе растеризации. Текстурная память оптимизирована под выборку 2D данных и имеет следующие возможности:

  1.  быстрая выборка значений фиксированного размера (байт, слово, двойное или учетверенное слово) из одномерного или двухмерного массива;
  2.  нормализованная адресация числами типа float в интервале [0,1).
  3.  аппаратная линейная или билинейная (в случае 2D) интерполяция соседних значений в случае нормализованной адресации;
  4.  аппаратная обработка выхода за границу массива с использованием двух режимов: clamp и wrap;

Текстурная память физически не отделена от глобальной памяти. Выделив функцией cudaMalloc некий участок глобальной памяти, можно затем указать с помощью функции cudaBindTexture, что данный участок теперь будет рассматриваться как текстурная память. Таким образом, получается, что размер текстурной памяти ограничивается только максимальным размером памяти, которую может выделить устройство (в общем случае сотни мегабайт).

Из недостатков текстурной памяти следует отметить, что из нее можно читать данные только встроенных в компилятор nvcc типов, имеющих размер 1, 2, 4, 8 или 16 байт, и только с помощью специальных функций — tex1D, tex2D или tex1Dfetch, tex2Dfetch. Иначе говоря, нельзя сделать указатель на текстурную память и получить его адрес произвольным образом (например, прочитав какую-либо структуру размером в 26 байт).

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

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

Например, можно создать текстуру с элементами uchar4, находящимися в интервале [0,255]. Затем можно их выбирать, используя нормализованную адресацию. Результатом будет значение типа float4, отображенное в интервал [0,1). Здесь используется стандартное математическое обозначение для интервала, где 0 включается, а 1 — нет.

Архитектура CUDA позволяет сделать обработку выхода за границы массива в двух режимах wrap и clamp. При использовании режима clamp происходит «схлопывание» значения до ближайшей границы. В режиме wrap координаты заворачиваются таким образом, что если координата x выходит за границу массива на N, то будет взят N-ый элемент массива. Т.е. фактически всегда берется остаток от деления на размер массива. Следует отметить, что это свойство текстурной памяти весьма полезно для реализации хэш-таблиц.

Библиотека CURAND

Библиотека входит в стандартный комплект разработчика программного обеспечения CUDA и представляет собой набор заголовочных файлов [18]. Данная библиотека предоставляет набор инструментов для простого и быстрого создания последовательностей псевдо и квази случайных чисел. Последовательность псевдослучайных чисел удовлетворяет большинству статистических свойств случайных последовательностей.

Библиотека CURAND функционально состоит из двух частей: библиотеки для хоста (центрального процессора) и библиотеки для устройства (графический адаптер).

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

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

  1. Создать генератор требуемого типа при помощи функции curandCreateGenerator()
  2. Установить опции генератора, например, использовать функцию curandSetPseudoRandomGeneratorSeed() для установки ключа (зерна)состояния генератора
  3. Выделить память графического адаптера при помощи вызова cudaMalloc()
  4. Создать случайные числа при помощи функции curandGenerate(), либо при помощи любой другой функции, обеспечивающей создание последовательностей случайных чисел
  5. Каким-либо требуемым образом использовать полученные случайные числа
  6. Если требуется, то создать больше случайных чисел
  7. Очистить используемые ресурсы при помощи curandDestroyGenerator()

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

Рассмотрим более подробно библиотеку для устройства. Для ее использования необходимо подключить заголовочный файл <curand_kernel.h>. Данный файл содержит функции для создания последовательностей псевдо и квази случайных чисел. Псевдослучайные числа могут быть созданы при помощи различных генераторов, предоставляемых данной библиотекой (XORWOW, MRG32k3a, MTGP32), так же возможно создание последовательностей подчиняющихся определенным законам распределения  (равномерное, нормальное) [18]. Для создания квази случайных чисел в библиотеки используются функции на основе последовательности Соболя.

Библиотека CUSP

Данная библиотека также поставляется вместе с инструментами разработчика CUDA и представляет собой библиотеку шаблонов Си++. Она  предоставляет широкие возможности по работе с разреженными (sparse) матрицами: хранение в различных форматах, конвертации между различными форматами, чтение и запись матриц из формата Matrix market (файлы .mtx), умножение матриц, хранящихся в разреженном формате между собой и заполненными векторами и многое другое [19]. Разработчиками реализованы следующие форматы хранения разреженных матриц:

  1. Разреженный строчный формат
  2. Разреженный столбцовый формат
  3. Диагональный (для хранения диагональных матриц)
  4.  ELL
  5. Гибридный (Hybrid)

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

Разреженные строчный и столбцовые форматы являются более гибкими и простыми в использовании, чем диагональный и EL. Гибридный формат (HYB) представляет собой сочетание формата ELL (быстрый) и разреженного столбцового (гибкий) и является хорошим выбором «по умолчанию».


Исследовательская часть. Тестирование параллельной реализации метода Монте-Карло и анализ результатов.

  1.  

Постановка эксперимента

В ходе экспериментов проводилось решение СЛАУ (1), в которой в качестве матрицы коэффициентов системы использовались различные матрицы, получающиеся при решении прикладных задач. Были использованы матрицы со следующих сайтов [24, 25].

Как было замечено в параграфе с описанием метода (2.7.3) для возможности решения СЛАУ методом Монте-Карло необходимо, чтобы матрица коэффициентов системы обладала диагональным преобладанием. Поэтому в случае если исходная матрица не обладает диагональным преобладанием, то производится преобразование матрицы к виду с диагональным преобладанием. Для этого к диагональному элементу каждой строки прибавляется сумма модулей недиагональных элементов данной строки со знаком диагонального элемента.

Вектор свободных частей системы (1) определялся следующим образом. Зададим вектор точного решения СЛАУ (1):

,             (70)

где  

Тогда, умножив матрицу коэффициентов  на вектор точного решения x, получим искомый вектор b:

Ax = b               (71)

Обзор использованных матриц

Для большей наглядности сведем данные о матрицах в таблицу 1:

Таблица 1. Использованные матрицы

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

Рис. 12. Структура матрицы s1rmq4m1

Рис. 13. Структура матрицы bcsstk17

Рис. 14. Структура матрицы fidapm29

Рис. 15. Структура матрицы fidapm11

Рис. 16. Структура матрицы s3dkt3m2

Рис. 17. Структура матрицы BenElechi1

Конфигурация использованного оборудования

Для проведения экспериментов использовался компьютер со следующими характеристиками:

Процессор: Intel(R) Core2Quade Q9000, количество ядер – 4, частота ядра 2 ГГц.

Видеокарта: NVIDIA GeForce GT 240M, Compute Capability – 1.2, количество мультипроцессоров – 6, частота 1,21 ГГц.

Методика проведения экспериментов

Проводилось решение СЛАУ с матрицами коэффициентов и свободными частями описанными выше. Решение проводилось тремя различными методами: исследуемым методом Монте-Карло, методом GMRES и методом бисопряженных градиентов (BICG) из библиотеки CUSP. Измерялось время расчетов на графической карте при помощи механизма событий CUDA. Для всех матриц, кроме матриц BenElechi1и s3dkt3m2,  выполнялось 5 запусков, в результатах использованы средние значения. Для BenElechi1и s3dkt3m2 выполнялось 3 запуска.

Для метода Монте-Карло проводились расчеты с количеством реализаций случайного процесса 1000000. На графической карте выполнялись расчеты корней СЛАУ блоками по 100. Для методов GMRES и BICG использовались следующие критерии остановки: достижение количества итераций 10000 или достижение точности 10-6.

Также был проведен эксперимент для изучения зависимости времени решения от количества запущенных блоков (в каждом блоке 8 скалярных процессоров). Проводился расчет 100 корней СЛАУ при количестве реализаций случайного процесса 1000000, с различным количеством блоков в конфигурации ядра CUDA Эксперимент был проведен для одной матрицы:  fidapm11.

Ошибка решения СЛАУ методом Монте-Карло оценивалась при помощи относительной невязки – невязка вектора правой части B, рассчитанная по формуле: .

Результаты эксперимента

Таблица 2. Результаты эксперимента по решению СЛАУ

В таблице 2 символом * обозначено то, что метод не сошелся.

Рис.15. Время решения СЛАУ различных размерностей методом Монте-Карло

Рис.16. Время решения СЛАУ различных размерностей методом GMRES

Рис.17. Время решения СЛАУ различных размерностей методом BICG

Рис. 18. Ускорение

Выводы

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

  1. Зависимость времени решения СЛАУ от ее размерности для метода Монте-Карло линейная, что согласуется с теоретическими основами метода
  2. На графиках, изображенных на рисунках 16 и 17, видна квадратичная зависимость времени решения СЛАУ от ее размерности для методов GMRES и BICG
  3. Для СЛАУ небольших размерностей ( для GMRES,  для BICG) метод Монте-Карло оказывается менее эффективен чем итерационные методы.
  4.  Метод Монте-Карло показал более высокую надежность в отличие от методов GMRES, BICG, получив решение системы на всех матрицах

Технико-экономическое обоснование эффективности НИОКР

  1.  

Введение

Дипломная работа посвящена разработке и экспериментальному исследованию семейства численных методов решения СЛАУ большой размерности – методов Монте-Карло.

В основе данных методов лежит получение большого числа реализаций стохастического процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи. Методы используются во многих областях научной деятельности человека, например при решении задач химии, физики, математики, экономики и др. В рамках дипломной работы было проведено исследование применения метода для решения СЛАУ больших размеров при помощи графического адаптера. Его использование позволяет увеличить быстродействие решения задачи при минимизации затрат на аппаратную поддержку алгоритма. Фактически предложенные алгоритмы позволяют использовать маломощные пользовательские персональные компьютеры для решения серьезных задач.

Организационно-экономическая часть работы посвящена разработке комплекса мероприятий организационно–экономического и финансового планов, которые необходимо выполнить для разработки методов и алгоритмов решения СЛАУ на графических адаптерах компании NVIDIA методом Монте-Карло. Алгоритмы и методы реализуются при помощи технологии компании NVIDIA CUDA. Программное обеспечение, созданное в ходе НИОКР, разработано исключительно в интересах кафедры и не предназначено для последующей продажи или внедрения.

Расчет трудоемкости выполнения НИОКР

Для планирования продолжительности выполнения НИОКР используются расчетные и опытно-статистические нормативы. Однако по значительной части работ такие нормативы отсутствуют. Поэтому для определения продолжительности работ используются две оценки времени, выдаваемые ответственным исполнителем: минимальная и максимальная продолжительность работы. При этом оценки рассматриваются не как обязательство ответственного исполнителя, а как предложение, основанное на опыте, интуиции и на учете факторов, влияющих на продолжительность работы.

Рассмотрим перечень работ по всем этапам НИОКР:

  1.  техническое задание (ТЗ) – постановка задач проекта, определение основных положений и методик;
  2.  эскизное проектирование (ЭП) – выбор программных средств создания ПО, разработка принципиальных технических решений, комплексное исследование предметной области, формирование алгоритмов работы ПО;
  3.  техническое проектирование (ТП) – окончательный выбор технических решений, разработка диаграмм классов ПО;
  4.  рабочий проект (РП) -  непосредственная разработка алгоритмов и технологий, создание модулей программы;
  5.  экспериментальные исследования (ЭИ) – подготовка экспериментальной базы, исследования работы алгоритма, эксперименты по автоматизированному аннотированию документов, обобщение и оценка результатов экспериментов.

Рассчитываем ожидаемое время выполнения каждой работы tож:

, где

tmin – минимальная продолжительность работы, т.е. время, необходимое для выполнения работы при наиболее благоприятном стечении обстоятельств (час, дни, недели и т.д.);

tmax - максимальная продолжительность работы, т.е. время, необходимое для выполнения работы при наиболее неблагоприятном стечении обстоятельств (час, дни, недели и т.д.)

Для определения возможного разброса ожидаемого времени рассчитываем дисперсию (рассеивание) :

.

Для определения количества исполнителей и построения план-графика выполнения НИОКР необходимо рассчитать продолжительность каждого этапа работы (ТЗ, ТПр, ЭП, ТП, РП, ИОО, ИО, ТД). Требуемое количество исполнителей R по этапам определяется по формуле:

, где

- трудоемкость этапа, час;

- коэффициент дополнительных затрат (1.1<Кд<1.15);

- фонд рабочего времени исполнителя (176 часов в месяц);

- коэффициент выполнения норм .

В рамках данного проекта число исполнителей является постоянной величиной, заданной изначально – это один студент дипломник.

Результаты расчетов приведены в таблице 3.

Стадии

tmin, дни

tmax, дни

tож, дни

Количество исполнителей

 

Постановка задач проекта (ТЗ)

3

6

4

1

0,36

Выбор программных средств разработки ПО (ЭП)

3

5

4

1

0,16

Исследование предметной области (ЭП)

5

18

10

1

6,76

Разработка методов и алгоритмов (ЭП)

10

23

15

1

6,76

Разработка диаграмм UML (ТП)

4

9

6

1

1

Разработка версии программы для работы с заполненными матрицами (РП)

4

14

8

1

4

Разработка версии программы для работы с разреженными матрицами (РП)

10

17

13

1

1,96

Разработка модуля загрузки исходных данных в РСФ (РП)

7

15

10

1

2,56

Реализация генераторов случайных чисел для GPU (РП)

2

2

2

1

0

Реализация метода Монте-Карло для GPU (РП)

10

15

12

1

1

Исследование работы метода Монте-Карло на CPU (ЭИ)

3

5

4

1

0,16

Исследование работы метода Монте-Карло на GPU (ЭИ)

3

5

4

1

0,16

Обобщение и оценка результатов исследований (ЭИ)

3

5

4

1

0,16

Итого

96 рабочих дней

Таблица 3. Продолжительность этапов работ

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

На основе полученных данных строим план-график выполнения НИОКР (рисунок 19). Суммарное ожидаемое время выполнения комплекса проектных работ составляет 96 дней.

Рисунок 19. План выполнения НИОКР, диаграмма Ганта

Расчет затрат на выполнение НИОКР

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

  1.  Материальные затраты (МЗ).
  2.  Прочие затраты (ПЗ).
  3.  Фонд заработной платы (ФЗ).
  4.  Отчисления в фонды (ОТЧ).
  5.  Амортизационные отчисления (АО).
  6.  Полная себестоимость работы (С).

Материальные затраты (МЗ)

К этой статье расходов относятся затраты, связанные с приобретением специального оборудования (специальных стендов, приборов, установок), которое необходимо для проведения научных (экспериментальных) работ только по данной теме. Поскольку в рамках проекта разрабатывалось только одно направление то все затраты на оборудование не вошедшее в основные фонды выносятся в данный раздел. Расчет приведен в таблице 4. 

№ п/п

Перечень оборудования

Единица измерения

Кол-во

Цена ед., руб.

Сумма, руб.

1

Персональный компьютер

шт.

1

25000

25000

Итого:

25000

Таблица 4. Таблица материальных затрат

В ходе разработки программного обеспечения, реализующего разрабатываемые методы решения СЛАУ, было использовано свободное программное обеспечение на базе лицензий CPL (Common Public License) и GPL (General Public License). Разработка ПО велась в интегрированной среде Eclipse, диаграммы UML были созданы в свободном редакторе Umbrello UML Modeller. Таким образом, на покупку необходимого ПО не было затрачено материальных средств.

МЗ =25000 руб.

Прочие затраты (ПЗ)

Материалы и покупные изделия, используемые для выполнения НИОКР, оцениваются по действующим оптовым или договорным ценам. Расчет затрат на материалы приведен в таблице 5.

№ п/п

Перечень оборудования

Единица измерения

Кол-во

Цена ед., руб.

Сумма, руб.

1

USB-накопитель

шт.

1

500

500

2

Диск DVD-R

шт.

1

20

20

Итого:

520

Таблица 5. Прочие затраты

Также необходимо учесть затраты на подключение к сети интернет. Они составляют 660 руб. в месяц. Работы по НИОКР занимали пять месяцев. Так как оплата производится в момент начала месяца, то в данном случае можно принять срок равным пяти месяцам. Поэтому затраты на подключение будут равны 660*5 = 3300 руб.

ПЗ = 520 + 3300 = 3820 руб.

Фонд заработной платы (ФЗ)

В статью «Основная заработная плата» включается основная заработная плата всех исполнителей, непосредственно занятых работами по НИОКР, с учётом их должностного оклада и времени участия в работе.

В статье «Дополнительная заработная плата» учитываются все выплаты непосредственным исполнителям за время, не проработанное на производстве. Дополнительные выплаты определяются как произведение основной заработной платы на коэффициент отчислений на дополнительную зарплату. Примем этот коэффициент равным 0,2.

За месячный оклад примем среднюю заработную плату инженера-программиста – 55000 рублей. Примем среднее количество рабочих дней в месяце . Рассчитанные значения заработной платы приведены в таблице 6.

Исполнитель

Месячный оклад, руб

Дневная заработная плата, руб

Продолжительность работы, дней

Основная заработная плата, руб

Дополнительная заработная плата, руб

Инженер–программист

55000

2500

96

240000

48000

Таблица 6. Фонд заработной платы

Получаем расходы на заработную плату:

СЗП = СЗО + СЗД = 240000+48000 = 288000 руб.

Амортизационные отчисления (АО)

Амортизационные отчисления производятся предприятиями ежемесячно исходя из установленных норм амортизации и балансовой (первоначальной или восстановительной) стоимости основных фондов по отдельным группам или инвентарным объектам, состоящим на балансе предприятия. Нормы амортизации устанавливаются государством и они едины для всех предприятий и организаций.

НАИМЕНОВАНИЕ ОБОРУДОВАНИЯ

Норма амортиза-ционных отчислений

Физико-термическое оборудование для производства изделий микроэлектроники и полупроводниковых приборов

28,2

Контрольно-измерительное и испытательно-тренировочное оборудование для производства электронной техники

27,5

Оборудование для измерения электрофизических параметров полупроводниковых приборов

27,3

Оборудование для механической обработки полупроводниковых материалов

23,9

Вакуумное технологическое оборудование для нанесения тонких пленок

24,3

Оборудование для производства фотошаблонов

23,4

Сборочное оборудование для производства полупроводниковых и электровакуумных приборов

23,8

Электронные генераторы, стабилизированные источники питания, тиристорные выпрямители, регуляторы напряжения

15,5

Прочее спецтехнологическое оборудование для производства изделий электронной техники

13,1

Контрольно-измерительная и испытательная аппаратура связи, сигнализации и блокировки:

  1.  Переносная

14,3

  1.  Стационарная

7,0

Лабораторное оборудование и приборы

20,0

Электронные цифровые вычислительные машины общего назначения, специализированные и управляющие

12,5

Таблица 7. Годовые нормы амортизационных отчислений по отдельным видам специального оборудования (% от первоначальной или восстановительной стоимости ОПФ)

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

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

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

Амортизационные отчисления определяются по формуле:

, где

- материальные затраты, руб.;

-норма годовых амортизационных отчислений, % (электронные цифровые вычислительные машины общего назначения, специализированные и управляющие 12,5%);

- машинное время, необходимое для выполнения НИОКР, час;

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

AO =25000 *0.125*(96*8)/ (22*8*12) = 1136 руб.

Отчисления в фонды (ОТЧ)

Единый социальный налог заменен страховыми взносами в ПФР, ФСС и фонды обязательного медицинского страхования России.

  1.  ПФР – отчисления в пенсионный фонд России составляют 22%.
  2.  ФСС – фонд социального страхования – 2,9%.
  3.  ФМС – федеральный фонд обязательного медицинского страхования – 5,1%.

Всего отчисления в фонды суммарно составляют 30% фонда заработной платы.

ФЗ = 288000 руб.

ПФР = ФЗ*0,22 = 288000 * 0,22 = 63360 руб.

ФСС = ФЗ*0,029 = 288000 * 0,029 = 8352 руб.

ФФОМС = ФЗ*0,051 = 288000 * 0,051 = 14688 руб.

Итого 63360+8352 +14688 = 86400 руб.

Полная себестоимость работы (С)

Полная себестоимость НИОКР определяется по следующей формуле:

С=МЗ+ПЗ+ФЗП+АО+ОТЧ.

№ п/п

Статьи затрат на НИОКР

Затраты, руб.

Затраты, %

1

Фонд заработной платы

288000

71,2

2

Отчисления в фонды

86400

21,4

3

Амортизационные отчисления

1136

0,3

4

Материальные затраты

25000

6,2

5

Прочие расходы

3820

0,9

Итого

404356

100

Таблица 8. Таблица затрат на НИОКР

Рисунок 20. Статьи затрат на НИОКР

Оценка технического уровня НИОКР

Разработка ПО в данной работе проводилась для нужд кафедры с целью проведения экспериментов с разработанным методом. Она не предполагает последующей реализации программы. Так как результаты НИОКР будут использованы кафедрой для собственных нужд, в организационно-экономической части оцениваются только научно-технические результаты НИОКР. Следует отметить, что уровень научно-технических результатов не всегда соответствует уровню экономических.

Технико-экономическая выгода от внедрения разработанного в дипломной работе метода выражается в уменьшении затрат машинного времени и ресурсов на решение задач линейной алгебры по решения СЛАУ.

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

Выводы

В результате расчетов получены следующие характеристики выполняемого проекта. Общие трудозатраты на выполнение проекта составляют 96 человеко-дней. В реализации проекта задействован один исполнитель – инженер-программист с заработной платой 55000 рублей в месяц. Себестоимость разработки составила 404356 рубля.

Промышленная экология и безопасность

  1.  

Введение

В данном разделе производится анализ вредных факторов, действующих на пользователя ПК, и рассматриваются вопросы проектирования средств защиты от воздействия этих факторов. В основе анализа лежат действующие санитарные правила и нормы СанПин 2.2.2./2.4.1340–03 «Гигиенические требования к персональным электронно–вычислительным машинам и организации работы», а также нормы противопожарной безопасности (НПБ 105–03) и электробезопасности (Правила устройства электроустановок (ПУЭ)).

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

Анализ основных факторов воздействия среды на оператора ПК

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

  1. нагрузка  на  опорно-двигательный  аппарат  человека: интенсивная работа с клавиатурой и "мышкой" может вызывать болевые ощущения в пальцах рук, кистях, запястьях, предплечьях и локтевых суставах. Длительное пребывание в неподвижной, неудобной позе приводит к усталости и болям в позвоночнике, шее, плечевых суставах и мышцах спины;
  2. физическое воздействие: компьютер является источником электромагнитного поля промышленной частоты, электромагнитного излучения радиодиапазона, электростатического и постоянного магнитного полей, рентгеновского излучения. Так же компьютер и периферийное оборудование могут создавать шум, а так же изменять микроклимат и ионизацию воздуха в рабочем помещении;
  3. напряженность труда: работа с компьютером предполагает визуальное восприятие и анализ больших объемов информации, что вызывает утомление зрительного аппарата человека и перегрузку его мозга и центральной нервной системы.

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

  1. параметры микроклимата;
  2.  допустимые уровни электромагнитное излучение;
  3.  эргономичность рабочего места и используемых устройств;
  4.  оптимальное размещение оборудования, входящего в состав рабочего места;
  5.  достаточное рабочее пространство, позволяющее осуществлять все необходимые движения и перемещения;
  6.  необходимо естественное и искусственное освещение для выполнения поставленных задач;
  7.  уровень акустического шума не должен превышать допустимого значения;
  8.  достаточная вентиляция рабочего места;
  9.  необходимая электробезопасность;
  10. необходимая пожаробезопасность.

Критерии проектирования освещения вычислительного центра

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

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

Таким образом, основными учитываемыми факторами являются:

  1.  параметры микроклимата
  2.  акустические параметры
  3.  электробезопасность
  4.  пожаробезопасность

Эти факторы рассматриваются как для оператора ПК, так и для технических средств вычислительной системы.

Общие положения организации рабочего места

Согласно СанПиН 2.2.2/2.4.1340-03, помещения для работы с компьютерами должны оборудоваться системами отопления, кондиционирования воздуха или эффективной приточно-вытяжной вентиляции. Расчет воздухообмена следует проводить по теплоизбыткам от оборудования, людей, солнечной радиации и искусственного освещения. Параметры микроклимата, ионного состава воздуха, содержание вредных веществ в нем должны отвечать нормативным требованиям. Звукоизоляция помещений и звукопоглощение ограждающих конструкций помещения должны отвечать гигиеническим требованиям и обеспечивать нормируемые параметры шума на рабочих местах. Помещения должны иметь естественное и искусственное освещение.

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

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

Требования к персональным электронно-вычислительным машинам

ПЭВМ должны соответствовать  требованиям  СанПиН 2.2.2/2.4. 1340-03, и каждый их тип подлежит санитарно-эпидемиологической экспертизе с оценкой в испытательных лабораториях, аккредитованных в установленном порядке.

Визуальные параметры ВДТ являются параметрами безопасности, и их неправильный выбор приводит к ухудшению здоровья пользователей. Для обеспечения надежного считывания информации при соответствующей степени комфортности ее восприятия СанПиН 2.2.2/2.4. 1340-03 определяет допустимые диапазоны визуальных параметров.

Допустимые визуальные параметры устройств отображения информации приведены в таблице 9.

п/п

Параметры

Допустимые значения

1

Яркость белого поля

Не менее 35 кд/кв. м

2

Неравномерность яркости рабочего поля

Не более ±20%

3

Контрастность (для монохромного режима)

Не менее 3:1

4

Временная нестабильность изображения (непреднамеренное изменение во времени яркости изображения на экране дисплея - мелькание)

Не должна фиксироваться

5

Пространственная нестабильность изображения (непреднамеренные изменения положения фрагментов изображения на экране)

Не более 2х 10E(-4L), где L - проектное расстояние наблюдения, мм

Таблица 9. Допустимые визуальные параметры устройств отображения информации

Для дисплеев на ЭЛТ частота обновления изображения должна быть не менее 75 Гц при всех режимах разрешения экрана, гарантируемых нормативной документацией на конкретный тип дисплея, и не менее 60 Гц для дисплеев на плоских дискретных экранах (жидкокристаллических, плазменных и т.п.).

Мощность экспозиционной дозы мягкого рентгеновского излучения в любой точке на расстоянии 0,05 м от экрана и корпуса ВДТ (на электронно- лучевой трубке) при любых положениях регулировочных устройств не должна превышать 1 мкЗв/час (100 мкР/час) (СанПиН 2.2.2/2.4. 1340-03).

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

Октавные полосы среднегеометрических частот, Гц

Допустимые значения уровней звукового давления, дБ

Реальные значения уровней звукового давления, дБ

31,5

86

88

63

71

74

125

61

58

250

54

59

500

49

52

1000

45

48

2000

42

40

4000

40

42

8000

38

41

Таблица 10. Допустимые значения уровней звукового давления в октавных полосах частот и уровня звука.

Измерение уровня звука и уровней звукового давления производится на расстоянии 50 см от поверхности оборудования и на высоте расположения источника(ов) звука. СанПиН 2.2.2/2.4. 1340-03.

Временные допустимые уровни электромагнитных полей (ЭМП), создаваемых ПЭВМ, согласно СанПиН 2.2.2/2.4. 1340-03 не должны превышать значений, представленных в табл. 11.

Наименование параметров

ВДУ ЭМП

Напряженность

электрического поля

в диапазоне частот 5 Гц - 2 кГц

25 В/м

в диапазоне частот 2 кГц - 400 кГц

2,5 В/м

Плотность магнитного потока

в диапазоне частот 5 Гц - 2 кГц

250 нТл

в диапазоне частот 2 кГц - 400 кГц

25 нТл

Электростатический потенциал экрана видеомонитора

500 В

Таблица 11. Временные допустимые уровни электромагнитных полей

Конструкция ПЭВМ должна обеспечивать возможность поворота корпуса в горизонтальной и вертикальной плоскости с фиксацией в заданном положении для обеспечения фронтального наблюдения экрана ВДТ.

Дизайн ПЭВМ должен предусматривать окраску корпуса в спокойные мягкие тона с диффузным рассеиванием света.

Корпус ПЭВМ, клавиатура и другие блоки и устройства ПЭВМ должны иметь матовую поверхность с коэффициентом отражения 0,4-0,6 и не иметь блестящих деталей, способных создавать блики. Конструкция ВДТ должна предусматривать регулирование яркости и контрастности (СанПиН 2.2.2/2.4. 1340-03).

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

Требования к микроклимату на рабочих местах, оборудованных ПЭВМ

В производственных помещениях, в которых работа с компьютером является основной (диспетчерские, операторские, расчетные, кабины и посты управления, залы вычислительной техники и др.), должны обеспечиваться оптимальные параметры микроклимата. СанПиН 2.2.2/2.4.1340–03 устанавливает категории тяжести работ не выше Iа.

Оптимальные параметры микроклимата во всех типах помещений с использованием ПЭВМ должны соответствовать нормам, приведенным в таблице 12.

Период года

Температура, ºС

Относительная влажность, %

Скорость движения воздуха, м/с

Холодный

22–24

40–60

<0,1

Тёплый

23–25

40–60

<0,1

Таблица 12. Оптимальные параметры микроклимата.

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

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

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

Уровни ионизации

Число ионов в 1 см3 воздуха помещения

положительных

отрицательных

Минимально необходимые

400

600

Оптимальные

1 500 – 3 000

3 000 – 5 000

Максимально допустимые

50 000

50 000

Таблица 13. Уровни содержания положительных и отрицательных аэроионов в воздухе.

  1.  
  2.  
  3.  
  4.  
    1.  
    2.  
    3.  

Обеспечение требований к размещению оборудования

Площадь на одно рабочее место с компьютером для взрослых пользователей должна составлять не менее 6,0 м2, а объем – не менее 20,0 м3.

Схемы размещения рабочих мест с ВДТ и ПЭВМ должны учитывать расстояния между рабочими столами с видеомониторами (в направлении тыла поверхности одного видеомонитора и экрана другого видеомонитора), которое должно быть не менее 2,0 м, а расстояние между боковыми поверхностями видеомониторов – не менее 1,2 м.

При работе с монитором в глазу происходят процессы аккомодации и конвергенции, постоянно напрягающие мышцы хрусталика глазодвигательные мышцы. Аккомодация – изменение геометрии хрусталика, при котором изображение фокусируется на сетчатке. Расслабление глаз возможно фокусировке на «мнимый» объект на расстоянии примерно 800 мм. Взгляд под углом 30о на объект, удалённый на 530мм расслабляет глазодвигательные мышцы. Поэтому экран видеомонитора должен находиться на расстоянии 600 – 700 мм от глаз пользователя на высоте его головы.

Зона досягаемости, сидящего за рабочим местом человека, составляет 350 – 400 мм. Ближней зоне соответствует область, охватываемая рукой при прижатом к туловищу локте, дальней зоне – область вытянутой руки. Поэтому клавиатуру следует располагать на поверхности стола на расстоянии 100 – 300 мм от края, обращенного к пользователю или на специальной выдвижной панели стола.

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

Рабочий стол должен иметь пространство для ног высотой не менее 600 мм, шириной – не менее 500 мм, глубиной на уровне колен – не менее 450 мм и на уровне вытянутых ног – не менее 650 мм.

Конструкция рабочего стула должна обеспечивать:

  1.  ширину и глубину поверхности сиденья не менее 400 мм;
  2.  поверхность сиденья с закругленным передним краем;
  3.  регулировку высоты поверхности сиденья в пределах 400 – 550 мм и углам наклона вперед до 15 град., и назад до 5 град.;
  4.  высоту опорной поверхности спинки 300 ± 20 мм, ширину – не менее 380 мм и радиус кривизны горизонтальной плоскости – 400 мм;
  5.  угол наклона спинки в вертикальной плоскости в пределах ± 30 градусов;
  6.  регулировку расстояния спинки от переднего края сиденья в пределах 260 – 400 мм;
  7.  стационарные или съемные подлокотники длиной не менее 250 мм и шириной 50 – 70 мм;
  8.  регулировка подлокотников по высоте над сиденьем в пределах 230 ± 30 мм и внутреннего расстояния между подлокотниками в пределах 350 – 500 мм;

Рабочие места по отношению к световым проёмам должны располагаться так, чтобы естественный свет падал сбоку, преимущественно слева (см. рис. 22).

Рисунок 22. Расположение рабочих мест по отношению к световым проёмам

Отделка помещений для работы с ПЭВМ.

Для внутренней отделки интерьера помещений, где расположены ПЭВМ, должны использоваться диффузно-отражающие материалы с коэффициентом отражения для потолка – 0,7 – 0,8; для стен – 0,5 – 0,6; для пола – 0,3 – 0,5.

Полимерные материалы используются для внутренней отделки интерьера помещений с ПЭВМ при наличии санитарно-эпидемиологического заключения.

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

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

Обеспечение электробезопасности.

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

Защита от поражения электрическим током обеспечивается различными способами, в том числе:

  1. размещением разъемов электропитания на тыльной стороне системного блока и монитора;
  2. применением надежных изоляционных материалов;
  3. использованием кабелей электропитания с заземляющими проводниками;
  4. использованием для электропитания устройств управления низковольтных напряжений (не более 12В);

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

Зануление электроустановки — преднамеренное электрическое соединение ее частей, нормально не находящихся под напряжением к нейтрали трансформатора через нулевой провод сети.

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

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

В сети 380/220 В недопустимо применять только заземление одних аппаратов и зануление других, так как в случае повреждения изоляции заземленного аппарата на нулевом проводе и зачтенном оборудовании может появиться напряжение. Заземленный корпус аппарата должен иметь металлическое соединение с нулевым проводом сети.

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

Обеспечение пожаробезопасности.

Помещения ВЦ относятся к категории "В" пожаробезопасности: в них находятся твердые сгораемые вещества, не способные взрываться. При работе с ПЭВМ необходимо соблюдать требования пожаробезопасности.

  1. Не следует загромождать горючими и легко воспламеняющимися материалами (бумага, расходные материалы печатающих устройств, магнитные носители информации и т.п.) рабочие места операторов ЭВМ, выходы, проемы, коридоры;
  2. Подступы к средствам пожаротушения, средствам связи, электрораспределительным устройствам, а также к эвакуационным путям должны быть всегда свободны;
  3. Имеющиеся деревянные звукопоглощающие настенные панели и другие детали должны быть пропитаны огнезащитным составом;
  4. В системе кондиционирования должны быть предусмотрены клапаны для перекрытия воздухопроводов при пожаре. Противопожарные клапаны в системах кондиционирования должны закрываться вручную, дистанционно с пульта дежурного или автоматически при достижении температуры воздуха в помещении 70...80 гр. Цельсия;
  5. Рекомендуется установить блокировку на систему электропитания ЭВМ, обеспечивающую отключение аппаратуры от сети электропитания при возникновении пожара.

 Обеспечение допустимого уровня шума

При выполнении основной работы на ВДТ и ПЭВМ уровень шума на рабочем месте не должен превышать 50 дБа. На рабочих местах в помещениях для размещения шумных агрегатов вычислительных машин (АЦПУ, принтеры и т.п.) уровень шума не должен превышать 75 дБА. Шумящее оборудование (АЦПУ, принтеры и т.п.), уровни шума которого превышают нормированные, должно находиться вне помещения с ВДТ и ПЭВМ.

Допустимые значения уровней звукового давления в октавных полосах частот и уровня звука, создаваемого ПЭВМ приведены в таблице 6.4.

Уровни звукового давления в октавных полосах со среднегеометрическими частотами

Уровни звука в дБА

31,5 Гц

63Гц

125 Гц

250 Гц

500Гц

1000 Гц

2000 Гц

4000 Гц

8000 Гц

86 дБ

71 дБ

61 дБ

54 дБ

49 дБ

45 дБ

42 дБ

40 дБ

38 дБ

50

Таблица 14. Допустимые значения уровней звукового давления и уровня звука

Измерение уровня звука и уровней звукового давления проводится на расстоянии 50см от поверхности оборудования и на высоте расположения источника (ков) звука.

Расчет системы освещения

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

Основным методом защиты зрения инженера во время работы является правильная организация системы освещения. В этой части раздела приведен расчет требуемой системы освещения для помещения, в котором проводилась работа над дипломным проектом. Помещение представляет собой малую аудиторию с вычислительной техникой и параметрами ШхДхВ – 4,2 х 6,5 х 3,8. Задачей данного светотехнического расчета является определение мощности всей осветительной установки для получения заданной освещенности на рабочих местах, при выбранном типе и расположении светильников.

Расчет освещенности производится в следующем порядке:

  1. Выбор источников света;
  2. Выбор системы освещения;
  3. Выбор типа осветительных приборов и определение высоты их подвеса над рабочей поверхностью;
  4. Размещение осветительных приборов и определение их количества;
  5. Выбор освещенности и коэффициента запаса;
  6. Расчет осветительной установки.

Выбор источников света

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

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

Выбор системы освещения

В практике проектирования осветительных установок используются следующие системы освещения:

  1.  общего освещения;
  2.  комбинированного освещения.

Общее освещение в свою очередь подразделяется на

  1.  общее равномерное (при равномерном распределении светового потока без учета положения оборудования);
  2.  общее локализованное (при распределении светового потока с учетом расположения рабочих мест).

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

Выбор осветительных приборов

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

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

  1. конструктивное исполнение светильника с учетом условий среды;
  2. светораспределение светильника;
  3. блесткость светильника;
  4. экономичность светильника.

Для нашего случая выбираем открытые двухламповые люминесцентные светильники ОДОР – они рекомендуются для нормальных помещений с хорошим отражением потолка и стен, допускаются при умеренной влажности и запыленности. Их минимальная высота подвеса составляет 3,5 метра.

Размещение осветительных приборов

При выборе расположения светильников необходимо руководствоваться двумя критериями:

Обеспечение высокого качества освещения, ограничение ослепленности и необходимой направленности света на рабочее место.

Наиболее экономичное создание нормированной освещенности.

Для равномерного общего освещения светильники с люминесцентными лампами должны располагаться рядами параллельно стенам с окнами.

В зависимости от типа светильников существует наивыгоднейшее относительное расстояние между светильниками

,

где L – расстояние между соседними светильниками;

h – высота подвеса светильника над рабочей поверхностью.

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

Для светильников ОДОР = 1,4.  Показатель для светильников ОДОР не используется. Таким образом, имеем:

h = H – 0,75 = 3,8 – 0,75 = 3,05 (м), где 0,75 – высота стола

L = 1,4 * h = 1,4 * 3,05 = 4,27 (м)

Двухламповые светильники располагаем в два ряда (по 3 светильника в каждом): всего 6 светильников, 12 ламп.

Рисунок 23. Расположение рабочих мест по отношению к световым  проёмам. Выбор освещенности и коэффициента запаса

Выбор освещенности и коэффициента запаса

Основные требования и значения нормируемой освещенности рабочих поверхностей изложены в санитарных нормах и правилах. Нормированная минимальная освещенность (Лк) определяется по таблице 1 разд.5.3 СниП 23-05-95. Работу инженера, в соответствии с этой таблицей, можно отнести к разряду точных работ (3 разряд зрительной работы, под разряд В), следовательно, минимальная освещенность должна быть Е = 300 Лк при использовании газоразрядных ламп. Коэффициент запаса, учитывающий уменьшение светового потока лампы в результате загрязнения светильников в процессе эксплуатации (его значение определяется по таблице 3 разд. 5.3 СНиП 23-05-95) в нашем случае равен  К = 1.4.

Расчет осветительной установки

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

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

Световой поток F двух ламп светильника рассчитывается по формуле

где EН – выбранная нормируемая освещенность, лк; EН = 300Лк (в соотв. с СанПиН 2.2.2.1340-03 раздел 6)

S – площадь помещения, м2;

k – коэффициент запаса;

z – отношение средней освещенности к минимальной (z = 1,1 – 1,15);

N – число светильников – 6 шт. согласно пункту 2.4;

- коэффициент использования светового потока ламп, зависящий от типа светильника, коэффициентов отражения потолка и стен и индекса помещения i;

Индекс помещения выражает геометрические соотношения в помещении и определяется как

где h – высота подвеса светильника над рабочей поверхностью;

A и B – характерные размеры помещения.

Производим расчеты:

,  принимаем , , исходя из чего по таблице определяем ,

(лм) (на один двухламповый светильник)

Подсчитав световой поток, подбираем ближайшую стандартную лампу по таблице 15.

Люминесцентные лампы

Тип лампы

Световой поток, лм

ЛДЦ 20

820

ЛД 20

920

ЛБ 20

1180

ЛДЦ 30

1450

ЛД 30

1640

ЛБ 30

2100

ЛДЦ 40

2100

ЛД 40

2340

ЛБ 40

3000

ЛДЦ 80

3560

ЛД 80

4070

ЛБ 80

5220

Таблица 15. Стандартные лампы

В практике допускается отклонение потока выбранной лампы от расчетного до –10 и +20%, в противном случае задается другая схема расположения светильников. В нашем случае для двухлампового светильника выбираем лампу ЛДЦ 80. Тогда световой поток двухлампового светильника составляет F = 3560*2 = 7120 (лм).

В конце расчета подсчитаем фактическое значение минимальной освещенности рабочей поверхности с учетом выбранной лампы:

315 (ЛК)

6781

2

3560

300

РАСЧЕТНЫЙ

ВЫБРАННЫЙ

Н

МИН

F

F

E

E

Потребная мощность всей осветительной установки (6 двухламповых светильников):

960 (Вт)

12

80

N

P

P

где P – мощность одной лампы.

Утилизация ртутных ламп

Ртуть — один из наиболее хорошо изученных токсикантов. Металлическая ртуть и её соединения относятся к веществам 1 класса опасности. Основной путь поступления в организм — ингаляционный

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

Беспокойство вызывает хранение отработанных люминесцентных ламп, отнесенных к отходам 1 класса опасности.

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

Существующие методы демеркуризации включают механический сбор видимых на глаз скоплений металлической ртути, химическую демеркуризацию — обработку помещений растворами окислителей, хлорирующих реагентов (10%–ный раствор перманганата калия, 20%–ный раствор хлорного железа, 5–10%–ный раствор моно– и дихлорамина), а также порошком серы. Образующиеся при этом соединения ртути нелетучи, но оксид и хлорид ртути токсичны при попадании в желудок и, кроме того, могут вновь восстанавливаться до металлической ртути.

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

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

В результате переработки и дезактивации отработанных люминесцентных ламп получают крошку – отход. Полученная крошка применяется в качестве наполнителя в количестве не более 4% в бетонные и асфальтобетонные смеси, используемые при строительстве дорог.

Выводы

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

В результате проведенных расчетов была разработана осветительная установка, состоящая из 6-ти двухламповых светильников общей потребляемой мощностью 960 Ватт. Фактическое значение минимальной освещенности рабочей поверхности при использовании такой установки составляет 315 Лк, при норме 300 Лк.

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

Заключение

В конструкторской части работы был произведен краткий обзор численных методов решения СЛАУ и метода Монте-Карло в частности. Была разработана и приведена структура программы, а также описана программная реализация параллельной версии метода для архитектуры CUDA.

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

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

В разделе ТЭО НИОКР выполнены расчеты трудоемкости и затрат на выполнение НИОКР, а также произведена оценка технического уровня НИОКР.


Литература

  1. Самарский А.А., Гулин А.В.  Численные методы: Учеб. пособие для вузов.—М.: Наука, 1989 г.
  2. Бахвалов Н.С. Численные методы. – М.: Наука, 1975 г.
  3. Д. Каханер, К. Моулер, С. Нэш.  Численные методы и программное обеспечение.–М.:Мир,2001.–575с.
  4. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). М.: Высшая школа, 2000. 266с.
  5.  Сборник задач по методам вычислений (под ред. Монастырного П.И.)  М.: Наука, 1994.  320с.
  6. А. С. Хаусхолдер, Основы численного анализа, ИЛ,М., 1956, гл. VIII.
  7. В. Э. Мил н. Численное решение дифференциальных уравнений. Приложение В, ИЛ, М., 1955.
  8. Ю. А. Шрейдер, Метод статистических испытаний (Монте-Карло), Приборостроение, №7 A956).
  9. Современная математика для инженеров. Под ред. Э. Ф. Беккенбаха, ИЛ, М., 1958. Дж. В. Браун, Методы Монте-Карло.
  10. Б.П. Демидович, И.А. Марон. «Основы вычислительной математики». Издательство «Наука», 1966.
  11. И.М. Соболь. «Численные методы Монте-Карло». Издательство «Наука», 1973
  12. В.М Заварыкин. «Численные методы». Просвещение, 1990
  13. Образовательный комплекс «Параллельные численные методы» лекционные материалы, Нижегородский государственный университет им. Н.И. Лобачевского, под ред. Баркалова К.А.
  14.  Jason Sanders,Edward Kandrot—CUDA by Example An Introduction to General-Purpose GPU Programming—2010, Addison-Wesley
  15.  Боресков А. В., Харламов А. А. «Основы работы с технологией CUDA» изд. ДМК Пресс 2010.
  16.  «NVIDIA CUDA Programming guide 4.1», NVIDIA corp.
  17.  «CUDA Toolkit 4.1 CURAND Guide», NVIDIA corp, January 2012.
  18.  http://code.google.com/p/cusp-library/wiki/QuickStartGuide
  19.  Aspects of Computational Science. Stichting Nationale Computer Faciliteiten, The Netherlands, 1995.
  20.  Kadioglu M., Mudrick S. On the implementation of the GMRES(m) method to elliptic equations in meteorology. J. of Comput. Phys., 102, 1992, 348-359.
  21. Чадов С.Н. «О решении разреженных линейных систем при помощи метода бисопряженных градиентов», Вестник «ИГЭУ», Вып. 3 2007 г.
  22.  Barrett R., Berry M., Chan T.F., et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition.
  23. Дж. Голуб, Ч. Ван Лоум, ред. Воеводина, «Матричные вычисления», Москва «МИР» 1999 г.
  24.  http://www.cise.ufl.edu/research/sparse/matrices/
  25.  http://math.nist.gov/MatrixMarket/

2 Существует ряд методов аналогичных методу Гаусса (например, метод оптимального исключения  [4] стр.31).


 

А также другие работы, которые могут Вас заинтересовать

24725. Предметная область психологии 71.5 KB
  занятие контрольнодиагностические задания Цели: теоретическое и практическое овладение знаниями знакомство с наукой психология связь психологии с другими науками Ключевые понятия: психология как наука предмет психологии задачи психологии. Методология и методы психологии: методология – наука о методах. психологии харакны след принципы: В основе лежат постулаты диалектического материализма Принцип развития психика – непрерывно изменяющ.
24726. Человек как предмет общей психологии 35.5 KB
  Предложите и обоснуйте проект проведения лекции по теме Человек как предмет общей психологии Тема: человек как предмет общей психологии лекция. Цель: человек как предмет общей психологии. Ключевые понятия: объект психологии; предмет психологии; модельное описание психического облика человека: лингвистическая картина психического облика человека описание состава человеческой души: Аристотель Платон Плотин; ингредиенты психического облика; психика. Основные тезисы и краткое их доказательство: Первым и важнейшим объектом психологии...
24727. ТЕМПЕРАМЕНТ 43.5 KB
  Адресат: студенты 1го курса психологического факультета Цели: знакомство студентов с понятием темперамент раскрытие этого понятия через его определение и свойства с помощью темперамента показать психологические личностные различия. Задачи: определение темперамента история представлений о темпераменте свойства темперамента. Ключевые понятия: темперт темпераментные свойства типы ВНД типы темпта.
24728. Личность 41 KB
  Задачи: определение подходов к пониманию личности понятия личность подходов выявляющих ядро личности закономерностей развития личности направления исследования личности. Ключевые понятия: личность; система смыслов черт планов отношений; индивид субъект деятельности индивидуальность; биологическое и социальное социализация личности. и краткое их доказательство: В психологии имеются разные подходы к пониманию личности: она м. Подходы выявляющие ядро личности можно систематизировать след.
24729. Тромбоцитопеническая пурпура 140 KB
  Заболевание начинается исподволь или остро с появления геморрагического синдрома: кровоизлияния в кожу или слизистые оболочки и кровотечения из них. Для ТП характерны кровотечения из слизистых оболочек. Наиболее часто у детей наблюдаются кровотечения из носа маточные кровотечения у девочек в пубертатном возрасте. Реже бывают желудочнокишечные и почечные кровотечения.
24730. Патология периода новорожденности 127 KB
  Слайд 2 Последствия перенесенной энцефалопатии в периоде новорожденности нарушения психики церебральные параличи эпилепсия другие заболевания головного мозга. Некоторые дети перенесшие внутричерепную травму остаются с нарушениями психики с церебральными параличами с эпилепсией и другими заболеваниями головного мозга. Механизм развития патологического процесса при внутричерепной травме новорожденных можно представит в виде следующей схемы: Слайд 4 Схема развития патологического процесса при повреждении нервной системы...
24731. ПРОБЛЕМЫ НЕОНАТОЛОГИИ 204 KB
  МЛАДЕНЧЕСКАЯ СМЕРТНОСТЬ И ПУТИ ЕЕ СНИЖЕНИЯ Основное назначение педиатрии и охраны здоровья детей и подростков состоит в том чтобы способствовать нормальному физическому и психическому развитию как можно большего числа родившихся детей. Достижения недостатки а также задачи будущей работы отражают показатели детской смертности то есть отношение числа детей умерших в течение первого года жизни к тысяче родившихся. смертность детей в возрасте до 1 года – показатель социального благополучия страны. Показатель ее рассчитывается на 1000...
24732. ПЕРИОДЫ ДЕТСТВА 128.5 KB
  Внеутробный этап: период новорожденности от рождения до 28го дня жизни; ранний неонатальный от рождения до 7го дня жизни; поздний неонатальный – с 8го до 28й дня жизни; период грудного возраста с 28го дня жизни до 12 мес; ранний детский возраст от 1 года до 3 лет; дошкольный возраст от 3 до 6 лет; 5 младший школьный возраст от 7 до 11 лет; старший школьный период подростковый пубертатный от 12 до 1718лет. В различные периоды развития отмечается неравномерное совершенствование отдельных органов и систем организма...
24733. ПИТАНИЕ ДЕТЕЙ ПЕРВОГО ГОДА ЖИЗНИ. ЕСТЕСТВЕННОЕ ВСКАРМЛИВАНИЕ 164 KB
  слайд 1 Условия для нормального вскармливания ребенка грудного возраста правильная организация вскармливания систематический контроль за вскармливанием культурный уровень матери материальные возможности матери Ошибки допущенные в самом начале исправляются с трудом или вообще неисправимы. Однако гладкая мускулатура у ребенка развита слабее и наблюдается определенная склонность к дистензии желудочнокишечного тракта. Слайд 4 Особенности кала ребенка находящегося на грудном вскармливании кал яичножелтого цвета не имеет...