Диплом: Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных - текст диплома. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Диплом

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

Банк рефератов / Компьютерные сети

Рубрики  Рубрики реферат банка

закрыть
Категория: Дипломная работа
Язык диплома: Русский
Дата добавления:   
 
Скачать
Архив Zip, 156 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной дипломной работы

Узнайте стоимость написания уникальной работы

Ульяновский Государственный Университет Факультет механико-математический Кафедра математ ической кибернетики и информатики Работа допущена к защите Зав . кафедрой Семушин И.В. (Ф.И.О .) (подпись ) (дата ) Д И П Л О М Н А Я Р А Б О Т А Оптимальное управление вычислениями в распределенных ____ ___вычислительных системах на основе графа потоков данных _____ (название темы ) Прикладная математика . 01.02. (наименование и номер специальности ) Проект выполнил студент ПМ -52 Никифоров Ю.В. группа подпись Ф.И.О. Руководитель ассистент Дулов Е.В . должность подпись Ф.И.О. Рецензент Шиняев С.А. подпись Ф.И.О. У Л Ь Я Н О В С К 2000 Введение Параллельный компьютер – это набор процессоров , которые могут работать совместно для решения вычислительн ых задач . Это определение достаточно общее , чтобы охватить и параллельные суперкомпьютеры с сотнями или тысячами процессоров , сети персональных ЭВМ , многопроцессорные рабочие станции , и другие параллельные системы . Параллельные компьютеры интересны тем , ч т о они позволяют концентрировать большие вычислительные ресурсы для решения важных вычислительных задач . Параллелизм совсем недавно был экзотической областью компьютерной науки , интересной , но очень далёкой для рядового программиста . Сегодняшнее направлени е развития приложений , архитектуры компьютеров и сетей показывает , что теперь это не так . Паралеллизм становится вездесущим , и параллельное программирование становится центральным звеном при разработке программ. Традиционно , достижения в области высокопрои зводительных вычислений мотивировалось задачами численного моделирования сложных систем , таких как погода , климат , маханические устройства , электронные схемы , производственные процессы и химические реакции . Однако , наиболее влиятельной движущей силой разр а ботки более быстрых компьютеров на сегодняшний день является потребность в коммерческих приложениях , которые требуют от компьютера возможности обработки больших объёмов данных изощрёнными способами . В число таких приложений входят видео конференции , совме с тная среда разработки , компьютерное диагностирование в медицине , параллельные базы данных со средствами поддержки принятия решений , продвинутая графика и виртуальная реальность , особенно в индустрии развлечений . Но несмотря на то , коммерческие приложения м ожет определять архитектуру большинства будущих параллельных компьютеров , традиционные научные приложения останутся важными потребителями технологии параллельных вычислений . Производительность наиболее быстрых компьютеров растёт экспоненциально с 1945 до наших дней , в среднем в 10 раз каждые пять лет . Нет сомнений , что этот рост будет продолжаться . Однако , для обеспечения этого роста архитектура компьютеров радикально меняется – от последовательной к параллельной. Важной тенденцией , меняющей лицо компьют еров , является огромное возрастание возможностей компьютерных сетей . Лишь недавно , высокоскоростные сети работали на скорости 10 Mbit в секунду ; в конце 90-х пропускная способность в 100 и 1000 Mbit в секунду стала обычным делом . Значительно возрасла и их надёжность . Эти достижения позволяют разрабатывать приложения , использующие процессоры на множестве удалённых компьютеров . Эта область параллельных вычислений называется распределённые вычисления . Основной задачей разработки программ , которые могут работат ь на множестве компьютеров одновременно , всё таки является задача параллельных вычислений . В этом отношении , два разных слова , параллельный и распределённый , сходятся. Данный короткий обзор тенденций развития приложений , архитектуры и сетей наводит на мыс ль , что параллелизм охватывает не только суперкомпьютеры , но и рабочие станции , персональные компьютеры и сети . Поставщики традиционных коммер ческих суперкомпьютеров (SMP, MPP, параллельных векторных ) достаточно быстро улучшают производительность , надежность и простоту использования своих продуктов . Однако у этих компьютеров есть один большой недостаток - цена , подчас недоступная для многих о бразовательных и научно-исследовательских организаций . Однако потребность в вычислительных ресурсах у этих организаций велика . Следует иметь в виду , что производительность персональных компьютеров на базе процессоров Intel в последние годы также значител ь но выросла . Такие компьютеры стали создавать серьезную конкуренцию рабочим станциям на базе RISC, особенно по показателю цена /производительность . Одновременно стала приобретать все большую популярность многозадачнаые ОС Windows 95, NT . Возникла идея создавать параллельные вычислительные системы (кластеры ) из общедоступных компьютеров на базе Intel и недорогих Ethernet-сетей . Оказалось , что на многих классах задач и при достаточном числе узлов такие системы дают производительность , сравнимую с суперкомпьютерной . Целью данной работы является создание системы поддержки выполнения параллельных алгоритмов для локальной сети персональных комп ьютеров . Реализация данной системы может применяться для решения специфических задач , характеризующихся высокой степенью регулярности . Класс таких задач довольно широк , он включает в себя такие задачи , как , например , обработка изображений , решение диффере н циальных уравнений , моделирование длительных во времени процессов , в том числе и в реальном времени , многие другие научные и инженерные задачи , а также другие виды потоковой обработки данных . Модель параллельного компьютера состоит из некоторого числа выч ислительных машин фон Ньюмана . Модель машины фон Ньюмана включает в себя центральный процессор ( Central Processing Unit ), соединённый с блоком памяти . Процессор выполняет программу , которая представляет собой последовательность операций чтения /записи над памяти . Эта простая модель обосновалась довольно прочно в течение последних 45 лет . Все вычислительные машины соединены сетью . Каждая машина выполняет свою собственную программу , которая может обращаться к локаль ной памяти , посылать и принимать данные по межмашинной сети . Понятие локальности – третье фундаментальное требование к параллельной программе , в дополнение к параллелизму и масштабируемости . Его важность зависит от отношения цены удалённого доступа к цене локального даступа к данным . Это отношение варьируется от 10:1 до 1000:1 в зависимости от относительной производительности локального компьютера , сети , и механизма , используемого для передачи и приёма данных через сеть . Эта идеализированная модель достато ч но хорошо согласуется с реальной архитектурой параллельного компьютера , в качестве которой выбрана локальная сеть компьютеров . Локальная сеть характеризуется высокой ценой удалённого доступа . Ethernet и ATM являются наиболее распространёнными сетевыми техн ологиями на сегодняшний день . Для сети Fast Ethernet 100 Mbits отношение времён удалённого и локального доступа в некоторых случаях приближается к 10:1, что почти не сказывается на эффективности параллельных алгоритмов . Что касается ЭВМ с многозадачной опер ационной системой , то она также подходит под модель фон Ньюмана , т.к . центральный процессор просто работает в режиме разделения времени . В работе приводится соответствующая математическая интерпретация данного факта. Основу математической модели параллельн ого алгоритма составляет граф потоков данных (ГПД ). В потоковой модели параллельная программа представляется набором вычислительных узлов-подзадач (далее задач ), которые имеют фиксированное количество информационных входов и выходов . Узлы выполняют одни и те же операции с разной поступающей на входы информацией , и выдают результаты на свои выходы , также в виде числовой информации . Эти входы и выходы называются , соответственно , входными и выходными портами . Таким образом , вычислительные узлы строго периодич н ы . Узлы соединены между собой каналами передачи информации , выходные порты со входными . В реальной системе узлы представляются программами , а каналы – потоками байтов данных. Две эти абстракции – задача и канал – до статочно хорошо отвечают требованиям модели параллельного программирования : механизм , позволяющий ясно выразить параллелизм и облегчить разработку масштабируемых и модульных программ , абстракции , с которыми легко работать , и которые соответствуют архитект у рной модели параллельного компьютера. Данная модель характеризуется следующими свойствами : 1. Параллельное вычисление состоит из одного или более одновременно исполняющихся задач (процессов ), число которых постоянно в течение времени выполнения программы . 2. Задача - это последовательная программа с локальными данными . Задача имеет входные и выходные порты , которые служат интерфейсом к среде процесса . 3. В дополнение к обычным операциям задача может выполнять следующие действия : послать сообщение чере з выходной порт , получить сообщение из входного порта , создать новый процесс и завершить процесс . 4. Посылающаяся операция асинхронная - она завершается сразу , не ожидая того , когда данные будут получены . Получающаяся операция синхронная : она блокирует п роцесс до момента поступления сообщения . 5. Пары из входного и выходного портов соединяются очередями сообщений , называемыми каналами . Каналы можно создавать и удалять . Ссылки на каналы (порты ) можно включать в сообщения , так что связность может изменить ся динамически . 6. Процессы можно распределять по физическим процессорам произвольным способами , причем используемое отображение (распределение ) не воздействует на семантику программы . В частности , множество процессов можно отобразить на одиночный процес сор . Рассмотрим некоторые другие свойства модели задача /канал : производительность , независимость от распределения , модульность и детерминизм. Производительность. Абстракции последовательного программирования , такие как процедуры и структуры данных , эффект ивны потому , что они могут просто и рационально отображаться на вычислительную машину фон Ньюмана . Задача и канал производят тот же эффект по отношению к параллельному компьютеру . Задача представляет собой кусок кода , который может выполняться последовате л ьно , на одном процессоре . Если две задачи , обменивающиеся данными , распределены на разные процессоры , то канал связи между ними воспроизводится как межпроцессорное взаимодействие ; а если на один процессор , то может использоваться более быстрый механизм. Не зависимость от распределения. Так как задачи взаимодействуют используя один и тот же механизм (каналы ) независимо от их расположения , результат выполнения программы не зависит от того , где задачи выполняются . Следовательно , процесс проектирования и реализа ции алгоритмов может не касаться количества процессоров , на которых алгоритм будет выполняться ; фактически , большинство реализаций алгоритмов состоят из намного большего числа задач , чем процессоров . Это прямая предпосылка к масштабируемости . Модульность. В модульном программировании , различные компоненты программы разрабатываются поотдельности , как независимые модули , затем они собъединяются для получения полной программы . Взаимодействия между модулями ограничены хорошо продуманными интерфейсами . Т.о . мо д ульность уменьшает сложность программ и облегчает повторное использование отлаженного кода . Задача является естественным строительным блоком . Задача инкапсулирует данные и код , который работает с этими данными ; порты , через которые она посылает и принимае т данные , составляют её интерфейс . Более того , в качестве модуля можно использовать более сложную структуру , реализующую какой-то алгоритм , и который имеет свой интерфейс . Определённое сходство существует и с объектно-ориентированной парадигмой программиро в ания. Детерминизм . Алгоритм или программа детерминирована , когда выполнение с определёнными входными данными всегда приводит к одним и тем же результатам . Попарные взаимодейтсвия в модели задача /канал позволяет относительно легко гарантировать детерминизм. Каждый канал соединяет только одного отправителя и одного принимающего , и принимающая задача блокируется пока не закончится операция приёма . Эти условия ослабляются тем , что в один и тот же входной порт могут передаваться данный по разным каналам , т.е . о т разных посылающих задач , но при этом формат данных должен быть один и тот же . Операция посылки данных в порт также может блокироваться , если принимающая задача , на другом конце канала , не успевает принимать и обрабатывать данные. Потоковая модель не единс твенный подход представления параллельных вычислений . Было предложено много других , отличающихся гибкостью , маханизмами взаимодействия задач , степенью разбиения на задачи (гранулярностью ), масштабируемостью , модульностью . Примеры других моделей параллель н ого программирования : передача сообщений , параллелизм данных , разделяемая память. Передача сообщений. В иностранной литературе её называют Message Passing Interface ( MPI ). Возможно , сегодня это самая популярная модель параллельного программирования . Как и в модели задача /канал , MPI программы состоят из множества задач , каждая из которых инкапсулирует локальные данные . Каждая задача имеет своё уникальное имя , и модет посылать и принимать сообщения от другой задачи путём указания её имени . В этом отношении , M PI просто вариация модели задача /канал – вместо операции "послать в канал ", используется операция "послать задаче X ". MPI не препядствует динамическому созданию задач , выполнению нескольких задач на одном процессоре или выполнение разных программ одними и теми же задачами . Но на практике большинство MPI систем создают фиксированное количество задач при запуске программы , и не позволяют создание и уничтожение задач во время выполнения программы . Эти системы реализуют модель типа "одна программа много данных " ( Single Program Multiple Data ), так как каждая задача выполняет одни и те же действия над разными поступающими данными . Это сильно перекликается с потоковой моделью параллельного программирования. Паралеллизм данных. Паралеллизм в данной модели использует ся тогда , когда одна операция применяется к нескольким элементам структуры данных , например , "добавить число ко всем элементам массива ". Т.о . программа состоит из последовательности подобных операторов . Так как каждый элемент данных можно интерпретировать как независимую задачу , присущая гранулярность вычислений мала , и понятие "локальности " не очевидно . Следовательно , специализированные компиляторы часто требуют от программиста информацию о том , как данные распределяются между процессорами , другими словам и , как данные должны разбиваться на задачи . Далее компилятор транслирует программу в SPMD формулировку , генерируя коммуникационный код автоматически. Разделяемая память. В модели разделяемой памяти задачи используют общее адресное пространство для асинхронн ого чтения и записи . Различные механизмы , такие как замки и семафоры , могут регулировать доступ к разделяемой памяти . Преимуществом данной модели для программиста яаляется то , что не нужно явно указывать источник и приёмник данных , эта модель может сильно упростить программирование . Однако , затрудняется понимание и управление обменом данных , а также затрудняется написание детерминированииых программ. Далее приводится несколько типичных примеров параллельных алгоритмов . Все они описываются в терминах модели потоков данных. Конечные разности. Рассматривается одномерная конечноразностная задача , в которой имеем вектор X (0) размерности N и должны вычислить вектор X ( T ) , где Т.о . мы должны периодически обновлять каждый элемент X , так чтобы на t +1 шаге обновление происходило только после того , как над соседними элементами выполнится шаг t . ГПД данн ого алгоритма состоит из N задач , по одной на каждый элемент X . i -тая задача получает значение X i (0) и вычисляет , за T шагов , значения X i (1) , X i (2) , … X i ( T ) . Значит , на шаге t , она должна получить значения X i -1 ( t ) и X i +1 ( t ) от задач i -1 и i +1 . Каждая зад ача i , за исключением 0 -й и N -1 -й , имеет по паре разнонаправленных левых ( left ) и правых ( right ) портов , как показано на рисунке , и на каждой итерации t выполняет следующие действия : 1) посылает данные X i ( t ) в свои левый и правые выходные порты ; 2) прини мает от своих X i -1 ( t ) и X i +1 ( t ) левого и правого соседа ; 3) использует полученные значения для вычисления X i ( t +1) . Заметим , что N задач могут выполняться независимо , с одним лишь ограничением на порядок выполнения , определяемом синхронизацией посредством операций приёма . Следовательно , выполнение детерминировано. Попарные взаимодействия. В данном примере используется похожая структура ГПД как в примере с конечными разностями , но требуется более сложный алгоритм обмена д анных . Многие задачи требуют вычисление всех N ( N -1) попарных взаимодействий I ( X i , X j ) между N векторами X o , X 1 ,… X N -1 . В случае , когда взаимодействия симметричны , I ( X i , X j ) = I ( X i , X j ) , и требуется вычислить только N ( N -1) / 2 взаимодействий . Например , в молекулярной динамике требуется вычислить суммарный вектор сил воздействующих на атом X i , определённый как : F ( X i , X j ) означает взаимное притяжение или отталкивание между атомами X i и X j ; в данном случае , F ( X i , X j ) = - F ( X i , X j ), взаимодействия симметричны. Простой параллельный алгоритм для общей задачи попарных взаимодействий состоит из N задач . Задача i получает значение X i и вычисляет набор I ( X i , X j ) | i j . Сначала можно подумать , так как задача требует информацию от каждой другой задачи , для этого должно быть созд ано N ( N -1) каналов . Однако , более экономичная структура ГПД использует только N каналов . Они соединяют все задачи в однонаправленное кольцо , так что каждая задача имеет по одному входному и выходному порту . Каждая задача сначала инициализирует буфер (для х ранения локальной переменной ) и аккуммулятор , в котором будет содержаться результат вычислений . Затем задача периодически : 1) посылает значение из буфера в свой выходной порт ; 2) принимает значение из входного порта и записывает его в буфер ; 3) вычисляе т функцию взаимодействия между принятым и локальным значением ; 4) использует вычисленное значение для обновления локального аккумулятора. Этот цикл посылки-приёма-вычисления повторяется N -1 раз , осуществляя перемещение по кольцу всех N значений X i . Кажда я задача видит их всех и способна вычислить все N -1 взаимодействия . Алгоритм выполняет N -1 операцию на каждую задачу. Если взаимодействия симметричны , то можно уменьшить в два раза количество вычислений и обменов данных путём улучшения структуры ГПД . Пре дположим для простоты , что N четно . Добавляется дополнительные N каналов , соединяющих каждую задачу с задачей , расположенной через [ N / 2] по кольцу . Каждый раз , когда вычисляется I ( X i , X j ) между локальным X i и принятым X j , вычисленное значение не только суммируется в аккумуляторе для X i , но и в другом аккумуляторе , который является противоположным с X j . После [ N / 2] итераций аккумуляторы , ассоциированные со своими противоположными значениями , возвратятся в свои начальные задачи через новые каналы и обхед инятся с локальными аккумуляторами . Следовательно , каждое симметричное взаимодействие вычислится только раз : либо как I ( X i , X j ) на вершине содержащей X i , либо I ( X j , X i ) на вершине содержащей X j . Параметрическое исследование В случае , когда множество з адач может работать независимо и без взаимодействия друг с другом , степень паралеллизма принимает предельное значение . Примером подобного паралеллизма может послужить , так называемое параметрическое исследование , в котором одни и те же вычисления должны б ы ть проведены для набора различных входных параметров . Значения параметров могут считываться из входногофайла , а результаты записываться в выходной файл. Если время выполнения одинаково и процессоры идентичны , то достаточно разпределить задачи по ровну на каждый процессор . В другой ситуации , можно выбрать структуру ГПД показанную на рисунке . Задачи I (входная ) и O (выходная ) должны считывать и записывать входной и выходной файл , соответственно . Каждая рабочая задача W период ически запрашивает значения параметров от задачи I , вычисляет используя их , а затем отсылает результаты задаче O . Так как время выполнения варьируется , входная и выходная задачи не могут расчитвать на правильный порядок поступления сообщений от рабочих зад ач . Используется соединение типа много-к-одному . Возможный в этом случае недетерминизм влияет всего лишь на порядок записи результатов в выходной файл , но не на сами вычисляемые результаты. Входная задача посылает следующий набор параметров после того как получит запрос от рабочей задачи . В это время рабочая задача просто ждёт поступления входных данных . Поэтому , иногда эффективность можно улучшить с помощью раннего запроса , когда следующий набор параметров запрашивается до того как они потребуются. В дан ной работе Формулируется модель параллельной программы , называемая потоковой , на основе графа потоков данных . Она основывается на интенсивностях трафика в каналах обмена данных между задачами . В работе показано , что условием оптимальности параллельного вы числительного процесса (ПВП ) является , как сбалансированность вычислительной нагрузки между процессорами , так и минимизация межпроцессорного обмена данных по сети . В системах с идентичными процессорами оптимальной является равномерная балансировка нагрузк и . В гетерогенных или нагруженных системах нагрузка должна распределяться в соответствии с текущей производительностью процессоров : на более мощные – большая нагрузка . Для учета ограниченной пропускной способности сети введён второй критерий оптимальности : минимизация потока данных между узлами сети. Для работы алгоритмов оптимизации необходимо количественно определить понятие перегрузки в ПВП . Перегрузки определяются с помощью изменерния среднего трафика (потока ), проходящего по каналам обмена данных . Точне е говоря , ма предполагаем , что статистика потоков во всех каналах-дугах ГПД меняется только из-за изменения распределения задач по процессорам (конфигурации ). В потоковых моделях делается неявное предположение , что статистика трафика в дугах ГПД , а также з агруженность задач и процессов , не меняется во времени . Такое допущение разумно , когда эта статистика меняется очень медленно по сравнению со средним временем , необходимым для перераспределения задач , т.е . перехода к другой конфигурации , и когда потоки из м еряются путём временного усреднения. Постановка задачи 1. Модель вычислительной среды Задан набор идентичных процессоров : P = P 1 , P 2 , … P N Между любыми процессорами P i и P j ( i j ) существует общий канал связи . Если объем передаваемых данных в единицу времени между P i и P j равен f ij , тогда ограничение на пропускную способность сети выражается как : , где f ij – максимальная пропускная способность сети. 2. Модель вычислительной задачи Под вычислительной задачей понимается последовательная программа , которая может выполняться на любом из процесс оров сети . Она реализует какую-либо фиксированную операцию : вычислительный процесс , загрузку данных , вывод на экран и т.п . Назовем эту программу задачей . Задача z имеет наборы входных и выходных портов , посредством которых она получает входные данные и вы дает результаты своей работы , соответственно . Задача может не иметь входных портов , когда она является стартовой . При этом она должна иметь хотя бы один выходной порт . Но обратное неверно – признак стартовой задачи может иметь и задача с входными портами . А если задача не имеет выходных портов , то она является завершающей или замыкающей . При этом она должна иметь хотя бы один входной порт . Стартовые задачи обычно осуществляют загрузку входных данных из файлов или запрашивая их у пользователя , либо самостоят ельно генерируя их . Замыкающие задачи , как правило сохраняют результаты работы параллельного алгоритма в файл или выводят их на экран . Но , вообще , содержание задач не играет большой роли в данной модели , – это предоставляется решать программисту параллель н ого алгоритма . Роль генераторов данных и интерпретации результатов может выполнять любая из задач . В программе обязательно должна быть хотя бы одна стартовая задача , но может совсем не быть замыкающих . Параллельный алгоритм завершается , если завершены все задачи , помеченые признаком стартовая . С другой стороны завершить выполнение параллельного алгоритма можно прерыванием выполнения всех задач. Входные и выходные данные представляются порциями определенного размера . Рассмотрим задачу с несколькими входными и выходными портами . Схематическое изображение задачи показано на рисунке . В момент , когда поступают порции данных во все входные порты , задача приступает к их обработке . Пусть это будет какой-то вычислительный про ц есс . После окончания вычислений , их результаты направляются в соответствующие выходные порты , также в виде порций данных определенного размера. Процесс обработки данных в задаче должен быть периодическим . Т.е . после обработки очередной порции данных задач а ожидает следующей . При этом во время этого ожидания процессорное время данной задачей не используется. Рассмотр им математические соотношения для модели простой вычислительной задачи – с единственным входным и выходным портом . Пусть входные порции данных поступают в моменты времени t i и имеют объем в байтах M i , i = 0, 1, 2, … . Время обработки i -той порции д анных i . Последовательность i представляет собой интервалы поступления входных данных . Заметим , что так как в модели предполагается , что данные не могут накапливаться во входном буфере , и это соответствует реальному программному механизму передачи данных. Подробнее , это значит , что скорос ть выдачи данных задачей генератором будет равняться скорости обработки данных задачей приемником . Задача генератор может приступить к выдаче очередной порции данных до того момента , как задача приемник запросит входные данные . В этом случае протокол обмен а данных затормозит выдачу , а этим и саму задачу генератор , т.к . операция посылки данных в порт является блокирующей . Временная диаграмма процесса поступления и обработки данных показана на рисунке. Процесс обмена по каналу данных характеризуется скоростью обмена ил и потоком F , который определяется следующими соотношениями : , где F i – мгновенный поток в момент времени ti , F – средний поток на интервале [ t 0 , t k ) ; , где F max – средний максимальный поток , который может обрабатывать задача при текущем времени обработки i . Эффективность работы задачи при заданном входном потоке определяется отношением чистого времени вычислений ко всему време ни работы : где – чистое время вычислений , – интерв ал работы задачи ; таким образом , ( - ) – время простоя задачи, где e – эффективность работы задачи на интервале времени [ t 0 , t k ) . Существует прямо-пропорциональная зависимость между вх одным и выходным потоками задачи . Это следует из характера обработки данных – на каждую порцию входных данных вычисляется порция выходных , определенного размера . Если N i – размер i -той порции выходных данных , тогда : где F out – средний выходной поток за время . Следовательно , коэффициент обработки стремится к следующему среднему значению s при : Коэффициент s является постоянным для данной задачи , при фиксированных размерах входных и выходных порций данных , т.е . M i = M j и N i = N j для i j . Как видно из (2.2) период поступления данных не может превышать периода их обработки , поэтому входной поток F ограничен максимальным потоком F max . Из пропорциональности выходного потока входному следует , что и выходной ограничен : где F (с чертой ) – задаваемый входной поток , F - реальный входной поток . При взаимодействии двух задач соединенных каналом обмена данных , величина выходного потока первой задачи строго равна величине входного потока второй задачи : Таким образо м , при увеличении F 1 in , если F 2 in достиг максимума F 2 max , то F 1 in не может далее увеличиваться (см . рисунок ). А коэффициент обработки по входу z 1 и выходу z 2 равен произведению коэффициентов s 1 и s 2 первой и второй задачи , соответственно : 3. Модель графа потоков данных параллельного алгоритма (ГПД ) Граф потоков данных алгоритма является ориентированнным гр афом , в котором вершины представляют вычислительные задачи , а дуги – каналы обмена данных : G ( V , U ) ГПД параллельного алгоритма, V = v 1 , v 2 , … v M множество вершин-задач, U = u ji kl множество дуг-каналов обмена данных, где u ji kl – канал между задачам и v k и v l , соединяющий выходной порт j задачи v k со входным портом i задачи v l . Задача v k имеет m k входных портов под номерами 0,1,… m k -1 и n k выходных - 0,1,… n k -1 . Должны быть согласованы размеры передаваемых и принимаемых данных для каждого канала о бмена . Т.е . для u ji kl U , размер порции данных , исходящих из порта v k j , должны в точности равняться размерам входных данных в порт v l i . Данное определение ГПД не делает ограничений на наличие кра тных дуг и петель . Т.е . две задачи могут быть связаны несколькими однонаправленными каналами . А также канал может соединять собой выходной и входной порт одной и той же задачи . Ниже будет осуществляться переход к более удобному для анализа представлению Г П Д. 4. Характеристики параллельных вычислительных процессов (ПВП ) Любая вычислительная система состоит из набора , так называемых , функциональных устройств ( ФУ ) – это могут быть процессоры , каналы связи , память , накопители и т.п . – все , что участвует или вл ияет на процесс работы параллельного алгоритма . Для ФУ можно определить величину загруженности p на определенном интервале времени T , как отношение стоимости выполненной ФУ работы к максимальной стоимости работы , которая может быть выполнена данным ФУ за в ремя T . Стоимость работы может измеряться , например , в количестве арифметических операций , времени и т.п . Каждое ФУ характеризуется номинальной производительностью (далее производительность ), равной максимальной стоимости раб оты за единицу времени. Утверждение. Пусть в системе имеется N функциональных устройств ФУ 1 , ФУ 2 , … ФУ N с номи нальными производительностями 1 , 2 , … N , соответственно . Тогда загруженность всей системы p выражается через загруженности p i ФУ , входящих в систему , как где j – номинальная производительность системы. Доказательст во . Пусть за время T ФУ i выполнило работу стоимостью i . Максимальная стоимость работы , которую может выполнить ФУ i за T , равна i T . Вся система реально выполнила i , а максимально может - i T . Следовательно : ч.т.д. Следствие 1. Если система состоит из ФУ одинаковой производительности , то её загруженность равна среднему арифметическому загруженностей ФУ. Следствие 2. Чтобы выполнить работу заданной стоимости за минимальное время необходимо обес печить максимальную загруженность ФУ наибольшей производительности. Доказательство . ч.т.д. Важной характеристикой параллельного алгоритма является коэффициент ускорения (далее ускорение ): где T – время выполнения алгоритма на паралл ельной вычислительной системе , а T o – на простом , т.е . непараллельном или эталонном , ФУ . Если принять за 0 и - производительности эталонной и параллельной вычислительных систем , соответственно , т огда : где R max – максимальное ускорение , которое можно получить на данной параллельной системе ; реальное ускорение зависит от степени загруженности системы : Если R 1 , то параллельный алгоритм не имеет смысла выполнять на данной параллельной вычислительной системе . Возвращаясь к модели вычислительной задачи , выведем важное нер авенство , касающееся многозадачных операционных систем ЭВМ . Это неравенство характеризует загруженность процессора , если на нем работают несколько задач , а также взаимное влияние задач . Рассмотрим случай двух задач z 1 и z 2 , на процессоре P . Пусть они работ ают с периодами 1 и 2 , соответственно . Времена обработки данных 1 и 2 соответствуют работе каждой задачи поотдельности на данном про цессоре , т.е . без влияния другой задачи . В данном случае за стоимость берётся время выполнения задачи на данном процессоре , а точнее время чистых вычислений , т.о . стоимость задач равна 1 и 2 . Пр и выполнении задач z 1 и z 2 одновременно на многозадачном процессоре P , стоимость выполненой работы за время T равна : т.к . отношения T к i равны количеству циклов обработки за время T , при T >> 1 и 2 . Максимальная стоимость работы , которую мог бы выполнить процессор , выраженная в единицах времени , равна T . Следовательно , загруженность процессора : где p 1 и p 2 – загруженности , вносимые ка ждой из задач . То же неравенство в терминах входных потоков выглядит так : где 1 и 2 – входные потоки задач z 1 и z 2 , а x 1 и x 2 – соответствующие максимальные потоки при работе задачи на данном процессоре в одиночестве. Аналогично , для k задач : 5. Модель параллельных вычислений на основе ГПД 5.1. Распределение задач по процессорам Каждая задача должна работать на каком-либо из процессоров . Отсюда , распределение задач по процессором определяется функцией K (конфигурацией ): где V = v 1 , v 2 , … v M – набор задач параллельного алгоритма , P = P 1 , P 2 , … P N – набор процессоров параллельной вычислительной системы. Так им образом мощность множества всех конфигураций K : Обозначим множество задач , распределенных на процессор P j как : 5.2. Уточнение модели ГПД Преобразования и требования к графу потоков данных : 1) Связный ; 2) Конечный ; 3) Кратные однонаправленные дуги объединяются , сумма потоков объединяемых дуг приписывается эквивалентной дуге ; 4) Петли не будут учитываться и уда ляются , т.к . замыкание задачи саму на себя можно интерпретировать как часть внутреннего алгоритма задачи. Таким образом , получаем конечный связный ориентированный граф без кратных дуг и петель , т.е . простой орграф : G ( V , U ) ГПД параллельного алгоритма, V = v 1 , v 2 , … v M множество вершин-задач, U = u kl множество дуг-каналов обмена данных. Теперь можно определить матрицу потоков ГПД следующим образом : Следующие равенства определяют корректность задания графа потоков данных в данной модели : где l и q k – суммарный входной и выходной поток для каждой вершины ГПД ; постоянные матрицы – A , нормированая по строкам , и B , нормированая по столбцам , -задают отношения величин входных и выходных потоков каждой задачи : коэффициент обработки s k задачи v k задаётся следующим равенством : 5.3. Постановка задачи оптимизации Существуют следующие ограничения : ограничение на пропускную способность сети , где W – множество дуг , соединяющих те задачи , которые в данной конфигурации распределены на разные процессоры ; - неравенство для загруженности п роцессора P j , где k – суммарный входной поток , x k – максимальный суммарный входной поток , который может обрабатывать задача v k , работая на процессоре P j в одиночестве . Величина x k является постоянной для j , т.к . в модели вычислительной среды все процессоры идентичны. С данными ограничениями оптим изация осуществляется на дискретном множестве конфигураций K , нужно найти конфигурацию , для которой максимизируется суммарная загруженность p вычислительной системы : где p j – загруженность процессора P j . Отсюда формула для максимизации функционал а качества D ( K ) выглядит следующим образом : Утверждение. Матрица потоков F ГПД при любом распределении задач K представима в виде : где F o – любая матрица потоков удовлетворяющая определению данного ГПД , - скаляр , больший нуля. Доказательство. Следует из определения ГПД. Пусть F o нормирована так , что сумма всех её элементов равна единице . Тогда будет равно суммарному потоку в ГПД . Входные потоки задач k выражаются через базовые потоки как : Таким образом , функционал качества D ( K ) записывается следующим образом : Задача оптимизации эквивалентна максимизации скалярного коэффициента , при ограничениях : или где k – является постоянной величиной , характеризующая сложность задачи v k . Суммарный поток бу дет равняться минимальному из этих двух ограничений , так как больше он ничем не сдерживается . Отсюда следует , что задача оптимизации сводится к двум критериям : По первой формуле , требуется как можно более равномерно распределить вычислительную н агрузку по процессорам вычислительной системы . Вторая говорит о том , что при этом следует минимизировать поток по сети , т.е . межпроцессорный обмен данных. 5.4. Учёт фоновой загруженности процессоров Фоновая загруженность процессора означает , что помимо нашего ПВП на процессорах могут работать и другие вычислительные и другого рода процессы . Фоновая загруженность ( background load ) поддаётся измерению , и её можно представить числом p j b , 0 p j b < 1. Тогда неравенства (5.9) принимают вид : и , соответственно , критерий (5.16) j – ни что иное , как цена процессора P j . 5.5. Регулирование процента загрузки системы Если требуется не загружать систему как можно более полно только для выполнения нашего ПВП , а выделить под него только часть процессорных ресурсов , то можно принять в качестве предельно допустимого процента загрузки процессора число p j a , 0 < p j a 1. Регулиров ание имеет смысл проводить , если для какого-то j o выполняется : то есть , наблюдается превышение предела загрузки хотя бы одн ого из процессоров . Тогда регулирование должно привести к такой ситуации : и при этом для j o , соответствующего максимально загруженному процессору , будет выполняться : Это достигается снижением потока в раз , где вычисляется как : где ' – будет новый суммарный поток , а - управление потоком. Алгоритмы оптимизации Алгоритмы поиска оптимальной конфигурации или опт имального распределения задач по процессорам , будем называть алгоритмами распределения . Сначала приводятся статические алгоритмы распределения , для которых должны быть известны или эвристически заданы начальные параметры ГПД , такие как сложности задач k и матрица потоков F o . Статические алгоритмы могут использоваться для осуществоения начального распределения задач . Каждый алгоритм имеет свою специфику по сравнению с другими : в одних делается упор на первый из критерием эффект ивности – балансировка нагрузки между процессорами , в других на второй - минимизация потока в сети , или же на оба критерия сразу . На основе некоторых статических алгоритмов выводятся алгоритмы динамической корректировки распределения задач с учетом изменя ю щейся статистики потоков данных , загруженностей задач и процессоров , и т.п . Загруженность процессора вычисляется как сумма сложностей задач , распределенных на данный процессор . Во всех алгоритмах предполагается , что количество задач превышает количество п роцессоров , т.е . M > N . Для алгоритмов , в которых используются значения потоков в ГПД , необходимо преобразовать ГПД в неориентированный , когда дуги превращаются в рёбра . Кратные рёбра между парами вершин , если таковые имеются , объединяются , причём значения потоков суммируются . Это преобразование делается потому , что направление потоков данных между задачами безразлично – важно только его суммарное значение. 6.1. На основе минимаксного критерия Данный алгоритм опирается только на критерий балансировки проце ссорной нагрузки (5.16). На вход требуется только информация об относительных сложностях задач k , достаточны даже не точные , а их оценочные значения. Распределение осуществляется в соответствии с приоритетом задачи , который равен её сложности , по одной задаче за шаг . Алгоритм заканчивается через M шагов , где М – количество задач. Алгоритм : 1) Из ещё не распределённых задач взять задачу с наибольшей сложностью , пусть это задача v k 1 . 2) Выбрать процессор с наименьшей загружен ностью , пусть это процессор P j 1 . 3) Распределить задачу v k 1 на процессор P j 1 , т.е . K ( v k 1 )= P j 1 . 4) Возврат к 1, если ещё не все задачи распределены. Данный алгоритм можно применить для начального распределения задач при из вестных относительных сложностях задач. 6.2. На основе алгоритма построения остовного дерева максимального веса Приведённые далее алгоритмы , основанные на построении остовного дерева максимального веса , учитывают оба критерия оптимальности – они в разной степени осуществляют балансировку вычислительной нагрузки между процессорами и минимизацию потока данных в сети. Для следующего алгоритма требуется информация об отностительной сложности задач k , и также относительные величи ны потоков данных в ГПД f i o . Рассмотрим вариант алгоритма для частного случая вида графа потоков данных . ГПД представляет собой последовательность вершин , соединённых в цепь парами разнонаправленных каналов между каждой парой вершин . ГПД такого вида испо льзуют так называемые разностные параллельные алгоритмы . Вычисления производятся во всех вершинах одновременно , а по окончании очередного цикла задачи обмениваются результатами с задачами на двух соседних вершинах . Полученные от " соседей " данные используют ся в качестве входных для следующего цикла вычислений . Таким образом , обеспечивается стационарность потоков и загруженностей задач , и их относительные величины известны априори. Алгоритм для ГПД в виде цепи : 1) Выбрать N задач с максимальной сложностью , г де N – число процессоров , пусть это задачи v k 1 , v k 2 , … v kN . 2) Распределить эти задачи по одной на каждый процессор , т.е . K ( v ki )= P i . 3) Выбрать наименее загруженный процессор , пусть P j 1 . 4) Среди не распределённых задач , я вляющихся соседними для тех задач , которые уже распределены на процессор P j 1 , выбрать задачу с наибольшей сложностью , пусть это v ki . 5) Распределить v k 1 задачу на процессор P j 1 , т.е . K ( v ki )= P j 1 . 6) Переход к шагу 3, если е ще не все задачи распределены. Результат работы алгоритма для ГПД в виде цепи иллюстрирует рисунок , где в скобках показаны вершины , распределенные на один процессор. В данном примере алгоритма , основанного на построении остовного дерева максимального веса , используется принцип исключения дуг наибольшего веса из неравенства , ограничивающего суммарный поток в сети . Распределяя разные задачи на один и тот же процессор , мы их как бы объединяем , и соединяющая их дуга исключается из суммы межпроцессорных потоко в . Следовательно , если мы попытаемся исключить из этой суммы дуги с максимальными потоками , то этим обеспечивается минимизация потока данных в сети , т.е . второй критерий оптимальности . Кроме того , если при выборе процессора для распределения очередной зада ч и использовать минимаксный принцип , показанный в алгоритме (6.1), то мы приближаемся к удовлетворению и первого критерия оптимальности. Рассмотрим задачу построения остовного дерева с максимальной суммой весов дуг (МОД для краткости ). Вес дуги ( i , j ) в да нном случае – это поток f ij . Любое поддерево МОДа будет называться фрагментом . Заметим , что узел может рассматриваться как фрагмент . Дуга , имеющая один узел во фрагменте , а другой узел – вне этого фрагмента , называется дугой , уходящей от фрагмента. Утвержд ение. Пусть L – некоторый заданный фрагмент МОДа , а u = ( i , j ) – дуга максимального веса , уходящая от фрагмента L , причём узел j не входит в L . Тогда , если к L добавить дугу u и узел j , то получится фрагмент МОДа. Данное утверждение используется в качеств е основы для алгоритмов построения МОД . Идея алгоритма Крускаля состоит в том , что берутся несколько произвольных вершин как начальные фрагменты , и затем эти фрагменты увеличиваются путем последовательного добавления уходящих дуг минимального веса . Настан е т момент , когда какие-либо пары фрагментов соедининяются дугой , имеющей минимальный вес среди дуг , добавление которых не создаёт цикла . Алгоритм заканчивает работу после N -1 итерации. На этих принципах основан следующий алгоритм оптимального распределени я для ГПД любого вида : 1) Выбрать N задач с максимальной сложностью , где N – число процессоров , пусть это задачи v k 1 , v k 2 , … v kN . 2) Распределить эти задачи по одной на каждый процессор , т.е . K ( v ki )= P i . Вершины на каждом пр оцессоре (с номерами V ( j ) ) будут составлять N начальных фрагментов МОДа. 3) Выбрать наименее загруженный процессор , пусть P j 1 . 4) Найти ребро максимального веса , уходящее от j 1 -ого фрагмента , пусть на внешнем конце ребра находится задача v ki . 5) Распред елить v ki на процессор P j 1 , т.е . K ( v ki )= P j 1 . 6) Переход к шагу 3, если еще не все задачи распределены. 6.3. Алгоритм с улучшенной балансировкой нагрузки между процессорами Заметим , что на шаге 4 предыдущего алгоритма выбир ается задача не оптимальная в смысле балансировки нагрузки , в то время как в алгоритме для ГПД в виде цепи выбирается задача с максимальной сложностью из всех нераспределённых задач . Оптимизационные характеристики алгоритма можно улучшить , если построить о стовное дерево максимального веса заранее , а затем выполнить алгоритм распределения , аналогичный примеру для ГПД в виде цепи , приняв определение соседней вершины исходя из построенного остовного дерева . Единственным недостатком такого подхода является нео б ходимость постороения всего остовного дерева сразу , что для больших графов потребует много оперативной памяти. 6.4. Адаптивный алгоритм распределения Адаптивные или динамические алгоритмы оптимального распределения задач основаны на тех же принципах , что и статические . На каждой итерации динамического алгоритма в качестве начальных данных для используемого статического алгоритма берутся текущие усреднённые , с момента последней итерации , значения характеристик вычислительного процесса , такие как величины п о токов , загруженности задач и процессоров . Осуществлять полное перераспределение задач на каждой такой итерации нецелесообразно , так как это может занять много времени . Вместо этого перераспределяется определённое подмножество задач . Это подмножество соста в ляется из тех задач , перераспределение которых может привести к улучшению критерия качества . Затем над выбранным набором задач осуществляется алгоритм статического распределения. В приведённом здесь алгоритме выбирается одна из задач на основе текущих изме рений характеристик параллельного вычислительного процесса . Затем задача переназначается на другой процессор с помощью алгоритма , аналогичного одной итерации алгоритма (6.2). Выбор задачи кандидата на перераспределение является эвристическим – выбирается н аименее загруженная задача в наиболее загруженном процессоре . Перераспределив такую задачу на меннее загруженный процессор мы , таким образом , улучшим степень сбалансированности нагрузки . Кроме того , при этом будет наименьшая вероятность того , что это може т привести к колебательному режиму . Колебания в алгоритме распределения могут возникнуть в следующей ситуации . Предположим , по какому то принципу выбрана задача кандидат на перераспределение . Сначала её выполнение приостанавливается . Это действие последуе т за собой уменьшение загруженности того процессора , на котором работала эта задача . Затем задача запускается на другом процессоре , что приводит к увеличению его загруженности . В следующей итерации алгоритма может случиться так , что в качестве кандидата вы б ерется та же самая задача и перераспределится снова на старый процессор . Этот процесс может продолжаться довольно долго и отнять много времени на никчемные перескоки с одного процессора на другой . Данная ситуация наиболее вероятна в случае , когда задача в н осит большой вклад в загруженность процессора . Поэтому , одной из мер предотвращения таких ситуаций является выбор задачи с наименьшей загруженностью . Этот способ оправдывается , если изменения статистических характеристик параллельного вычислительного проц е сса происходит гораздо медленнее , чем период одной итерации алгоритма оптимизации. Еще одним способом улучшения оптимизационных характеристик алгоритма является перераспределение как можно большего числа задач за одну итерацию . Но , как уже говорилось , проц едура перераспределения отнимает много времени . Поэтому , число этих задач должно быть не слишком большим. Программная реализация и эксперименты 1. Программа Система управления параллельным вычислительным процессом (ПВП ) реализована для ОС Windows 95, о на состоит из двух частей : программы-монитора (далее монитор ) и программы-диспетчера (далее диспетчер ). Монитор должен работать на каждой ЭВМ локальной сети . Он выполняет запросы от диспетчера - на запуск задач , присоединение каналов , сбора статистики и д р . Монитор работает в полностью автоматическом режиме , и не требует от пользователя постоянного надзора . Диспетчер запускается перед началом работы параллельного алгоритма (ПА ), на любой из машин сети . Входными данными для диспетчера является граф потоков д анных (ГПД ) и скомпилированная библиотека задач ПА . Эти данные подготавливаются программистом в среде разработки ПА , основанной на пакете Borland Delphi. А затем , передаются диспетчеру с помощью специальной утилиты запуска , входящей в эту среду. После пол учения всех данных для выполнения ПА имеется возможность выбора алгоритма начального распределения и алгоритма динамической оптимизации , а также настройки других параметров диспетчера . Начальное распределение задач можно задать и вручную. Что касается вну тренней программной структуры системы , она состоит из трёх уровней : низкого , среднего , высокого и отображения . Функции низкого уровня : 1) запуск нового экземпляра задачи на любой ЭВМ локальной сети ; 2) соединение каналов обмена данных любых пар запущенны х задач ; 3) вычисление статистических данных в реальном времени. Функции среднего уровня : 1) организация и поддержка внутренней структуры ГПД ; 2) организация и поддержка текущей конфигурации параллельного алгоритма ; 3) организация абстрактного управле ния конфигурацией на основе ГПД , т.е . связь конфигурации и ГПД ; 4) внутреннее представление статистических данных. Функции высокого уровня : 1) реализация абстрактных алгоритмов начального распределения, 2) и оптимального управления. Функции уровня отоб ражения : 1) Организация интерфейса пользователя ; 2) Отображение текущей статистической информации в реальном времени. 2. Эксперименты Для проведения экспериментов были выбраны параллельные алгоритмы для численных методов вычислительной линейной алгеб ры (ВЛА ): параллельное умножение матриц , итерационный метод Якоби решению СЛУ , параллельный алгоритм факторизации матриц (LU-разложение ). Алгоритм параллельного умножения матриц имеет ГПД в виде звезды , эта задача аналогична задаче типа параметрического и сследования . Каждая задача типа Worker выполняет операцию скалярного или блочного умножения . Задача типа Manager выполняет генерацию самих перемножаемых матриц . В данном случае генерируются квадратные матрицы , заполненные случайными числами . Данный ПВП ха р актеризуется большими объёмами передаваемых данных , т.к . хорошее ускорение получается только при достаточно больших размерностях матриц , порядка нескольких сотен и тысяч . Поэтому с ним лучше работают алгоритмы оптимизации , оприрющиеся на критерий минимиза ц ии потоков (5.17). ГПД метода Якоби имеет циклический или кольцевой вид . С данным видом ГПД хорошо должен работать алгоритм на с упором на балансировку нагрузки. ГПД алгоритма LU-разложения имеет более сложный вид . В данном алгоритме наблюдается частые о бмены данных и быстрые процессы вычисления в каждой рабочей задаче . С данным типом алгоритма должны хорошо работать оба из предложенных критериев оптимальности. Заключение Оптимальное управление параллельными вычислительными процессами является одной и з сложнейших областей параллельных вычислений . Эффективность работы параллельного вычислительной программы (ПВП ) зависит не только от её параллельной структуры , но и от того , как реализуется её выполнение на конкретной вычислительной системе , и от многих в нешних факторов. Главное внимение в данной работе было сосредоточено на описание математической модели параллельного алгоритма на основе ГПД . Были строго матеметичеки выведены критерии оптимального выполнения ПВП в терминах потоков и загруженностей . А так же , предложены алгоритмы оптимального управления , опирающиеся на эти критерии . Один из этих алгоритмов реализован программно , спомощью чего были проведены эксперименты на реальной вычислительной сети . Эксперименты показали , что эффективная работа алгоритм о в оптимизации данного типа возможна только при стационарности ПВП во времени . По мере того , как параметры потоков данных и загруженностей процессоров начинают быстро меняться во времени , преимущества рассмотренных методов оптимального управления ПВП начин а ют исчезать . В таких случаях трудно рекомендовать какие-либо методы оптимизации , которые были бы одновременно эффективными и практичными. Литература. 1. Воеводин В.В . "Математические модели и методы в параллельных процессах ", М .:Наука , 1986, 296 с. 2. Бертсекас Д ., Галлагер Р . "Сети передачи данных ", М .:Мир , 1989, 544 с. 3. Ian Foster "Designing and Building Parallel Programs", 1995, в электронном виде . 4. Нечепуренко М.И ., Попков В.К ., Майнагашев С.М . и др . "Алгоритмы и программы решения задач на гр афах и сетях ", Новосибирск :Наука . Сиб . Отд-ние , 1990, 515 с. 5. Сергиенко И.В . "Математические модели и методы решения задач дискретной оптимизации ", Киев : Наукова Думка , 1988, 471 с. 6. Михалевич В.С . "Методы последовательной оптимизации в дискретных с етевых задачах оптимального распределения ресурсов ", М .:Наука , 1983, 208 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Включил телевизор - там Путин про Украину. Залез в интернет - там Путин про Украину. Купил «российскую газету» - там Путин про Украину. Сцуко, могу ли я хоть где-нибудь узнать о перспективах ремонта дорог в Тамбовской области?
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru