Методы и алгоритмы повышения эффективности вычислительной системы с параллельной архитектурой на основе модулярных структур данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Чернобровкин, Виталий Викторович

• Чернобровкин, Виталий Викторович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Чернобровкин, Виталий Викторович

ОГЛАВЛЕНИЕ

Основные обозначения и сокращения

Введение

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

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

1.2 Характеристики машинной архитектуры и параллельных вычислительных процессов

1.3 Обоснование применения модулярной арифметики в системах с параллельной машинной архитектурой

1.4 Постановка целей и задач исследования

Выводы

Глава 2 Теория распараллеливания многоразрядных вычислений на основе модулярной арифметики

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

2.2 Адаптация модулярной арифметики под вычислительные проблемы

2.3 Методы вычисления позиционных характеристик в модулярной арифметике

2.4 Методика преобразования числовых кодов в позиционные и непозиционные форматы

Выводы

Глава 3 Разработка алгоритмов немодульных операций

3.1 Метод распараллеливания поиска простых оснований

3.2 Алгоритмы деления в модулярной арифметике

3.3 Алгоритм вычета модулярной величины по большому модулю

3.4 Масштабирование целых положительных чисел

Выводы

Глава 4 Адаптация модулярных вычислительных моделей на параллельную машинную архитектуру

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

4.2 Особенности адаптации вычислительных алгоритмов под параллельную архитектуру GPU - процессоров

4.3 Адаптация модулярных вычислений на GPU-процессоры с помощью CUDA-технологии

4.4 Экспериментальные оценки производительности вычислительной системы INSERModCom

Выводы

Заключение

Список литературы

Приложения

Основные обозначения и сокращения

АО - арифметические операции

АУ - арифметическое устройство

ВС - вычислительные системы

ВУ - вычислительные устройства

ВТ- вычислительная техника

МА - модулярная арифметика

МВС - модульное возведение в степень

МО - модульные операции

МОИ - многоразрядная обработка информации

МСС - модулярная система счисления

МУ - модульное умножение

МЧ - многоразрядные числа

НО - немодульные операции

ПО - программное обеспечение

ПСС - позиционная система счисления

ПХ - позиционные характеристики

РЧ - рациональные числа

ЦОС - цифровая обработка сигналов

ВЯП - высокоуровневые языки программирования

GPU - графический процессор

N - множество натуральных чисел

Q - множество рациональных чисел

Z - множество целых чисел

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы повышения эффективности вычислительной системы с параллельной архитектурой на основе модулярных структур данных»

Введение

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

*

лельной машинной архитектурой. Одними из распространенных моделей со-> временных высокопроизводительных систем с параллельной архитектурой

являются системы компании NVIDIA, которые содержат в себе графические процессоры.

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

Данное обстоятельство обусловлено следующими причинами:

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

2. Существующее быстродействие вычислений составляет ~1017 операций.

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

- высокая стоимость разработки параллельных систем;

- потери производительности;

- Зависимость эффективности параллелизма от учета характерных свойств параллельных систем;

- существование последовательных вычислений.

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

Рассмотрим основные законы протекающие в вычислительной системе с параллельной архитектурой.

Так в соответствии с законом Амдала ускорение процесса вычислений при использовании р процессоров ограничивается величиной, 5 < 1/(/ + (1 — /)/р) где/есть доля последовательных вычислений в применяемом алгоритме обработки данных.

Напомним, что закон Амдала определяет принципиально важные для параллельных вычислений положения:

1. Ускорение зависит от потенциального параллелизма задачи (величины (1 — /) и параметров аппаратуры (числа процессоров р).

2. Предельное ускорение определяется свойствами задачи. Пусть, например, f = 0,2 (что является реальным значением), тогда ускорение не может превосходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи. Очевидной является чрезвычайно высокая чувствительность ускорения к изменению величины f.

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

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

спективной непозиционных систем является модулярная система счисления (МСС) [2,4,19,28,36,50,54,67].

Известно, что модулярная система счисления в настоящее время широко применяется для решения различных классов трудоемких задач в прикладных областях науки и техники [20,26,29,73,82]. Вычисления с многоразрядными числами, являются одной из областей, в которых модулярная система счисления имеет неоспоримые преимущества перед другими позицион-» ными системами счисления (ПСС) [51,54]. Благодаря своему естественному

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

»

приоритетная основа для высокопроизводительных компьютерных технологий, в частности таких как мультипроцессорная, суперкомпьютерная, С1ЮА - технология и другие [53,69,93,95].

В последнее время вопросами применения модулярной системы занимается большое количество научных, исследовательских и учебных учреждений, как у нас в стране, так и за рубежом. Однако сегодня существует еще значительный перечень задач, которые ограничивают широкое применение на практике вычислительных структур на базе модулярной арифметике [51,52,69,91]. Это, прежде всего:

1. Необходимость в проектировании модулярного сопроцессора;

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

3. определение позиционных характеристик;

4. выбор разрядности и количества модулей (оснований) для больших и сверхбольших вычислений;

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

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

ний многоядерных процессоров с распараллеливанием многоразрядной обработай информации.

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

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

ры данных и вычислительные операции на ее основе. Параллельные машин-

■

ные операции.

Методы исследования основываются на всестороннем анализе параллельных машинных архитектур и модулярной системы счисления, теории сравнений, математическом и компьютерном моделировании машинных операций, систематизации методов и алгоритмов параллельной обработки информации, исследования операций. Также применяются результаты исследований российских и зарубежных ученых (В.М.Амербаев, И.Я.Акушский, Д.И.Юдицкий, В.П.Гергель, В.В.Топорков, С.А.Инютин, Н.И.Червяков, М.ВЛобес, Donald Knuth, Richard E.Blahut).

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

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

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

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

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

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

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

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

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

Для достижения поставленной цели общая научная задача была разбита на ряд подзадач:

• Сравнительный анализ архитектуры параллельных машинных архитектур;

• Анализ модулярных вычислительных структур с точки зрения использования принципов параллельных вычислений.

• Разработка метода параллельного поиска простых чисел - оснований МСС.

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

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

• Адаптация моделей модулярных вычислительных структур под ар-• хитектуру многоядерных процессоров.

» На защиту выносятся следующие основные положения:

1. Выбор модели вычислительной системы с параллельной архитектурой на базе вРи-процессоров.

2. Обоснование применения целочисленной модулярной арифметики для обработки многоразрядной информации.

3. Метод параллельного поиска простых многоразрядных чисел.

4. Методы и алгоритмы расширения, масштабирования и деления чисел, представленных в модулярной системе счисления.

5. Модифицированные методы и алгоритмы вычисления позиционных характеристик.

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

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

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

2. Разработаны новые математические методы моделирования вычислительных структур, используемые для выполнения множества базисных немодульных процедур, вычисляемые на основе применения универ-

сальной позиционной характеристики (ПХ) и оценке качества их моделей.

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

4. Разработан метод параллельного поиска оснований МСС.

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

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

Практическая значимость. Разработанные модели, методы и алгоритмы параллельной обработки многоразрядной информации на основе модулярной вычислительной базы позволяют разрабатывать скоростные высокопроизводительные вычислительные системы нового класса, которые способны выполнять в реальном масштабе времени колоссальные объемы математических расчетов. Адаптация таких моделей на GPU - процессоры с помощью технологии CUDA приводит к сверхбольшой производительности. Разработанные методы и алгоритмы могут быть использованы для развития теории высокоскоростных вычислений, а соответственно и для развития различных областей, в которых они применяются:

• Проектирование баз данных, интеллектуальных и экспертных систем.

• Системах обработки сигналов радиолокации.

• Разработка и тестирование высокопроизводительных вычислительных систем.

• Разработка цифровых фильтров и цифровых арифметических преобразователей.

• Моделирования климата.

• Моделирование аэродинамических процессов.

• Криптография, криптоанализ.

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

Апробация работы. Основные результаты диссертационного исследования докладывались на X и XI окружных конференциях молодых ученых на базе СурГУ г.Сургут, декабрь 2010 г., ноябрь 2011 г. Региональной научно-практической конференции "Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов", проведенной 28 февраля 2012 г. на базе Алтайского государственного университета г.Барнаул, международной конференции "40-е Гагаринские чтения" на базе Московского Авиационного Технического Института им. Циолковского (МАТИ), апрель 2014 г., научно-практической конференции "Математические методы в нефтегазовом деле" посвященной П.Л. Чебышёву, состоявшейся в СурГУ, май 2014 г.

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, четырех приложений, списка сокращений и обозначений, а также списка литературы содержащего 102 наименования 33 из которых зарубежные и 6 приложений. Основная часть работы содержит 115 стра-

ниц машинописного текста иллюстрированного 23 рисунками и содержащего 14 таблиц. Общий объем диссертационной работы 141 страница.

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

В первой главе проводится всесторонний анализ структуры и производительности параллельных вычислительных систем на основе синтеза численных алгоритмов и вРИ - процессоров, который определил, что такой показатель эффективности системы как Я - ускорение обработки информации зависящий от двух параметров: - загруженности, я^ - пиковой производительности каждого вычислительного ядра системы имеет физический предел в рамках вычислительного машинного диапазона. В ходе исследования обнаружено, что для сохранения необходимого ускорения системы при ее максимальной загрузке необходимо наращивать количество вычислительных ядер. Но при тенденции уменьшения аппаратных затрат, такой вариант не будет иметь успеха у разработчиков вычислительных систем (ВС). Анализ вычислительных структур на основе МСС показал преимущества перед позиционными системами счисления и определил обоснование целесообразности ее применения для многоразрядной обработки информации. Арифметика, построенная на таких структурах, является арифметикой многократной точности, которая отражает: высокий уровень параллелизма, высокую точность, надежность и способность к самокоррекции, возможность реализации принципа конвейерной обработки информации.

Вторая глава отражает теорию распараллеливания вычислений многоразрядной числовой информации на базе модулярной арифметики. Представлен модулярный способ представления целых чисел: А, В < Р, где А, В - целые многоразрядные числа, Р = (р±' Рг '> ■■■>' Рп) ~ вычислительный диапазон модулярной системы.

На основе модулярной системы подробно рассмотрены принципы распараллеливания многоразрядных вычислений, выбор оптимального количества модулей и их разрядность. Универсальность представления многоразрядных чисел состоит в том, что все остатки являются малоразрядными числами и получаются не зависимо друг от друга, а значит параллельно. Отметим, что в кольце вычетов такие арифметические операции как аддитивные так и мультипликативные имеют те же свойства, что и в алгебраическом кольце. Также предлагается методика вычисления позиционных характеристик применяемых в модулярной арифметике (МА), которые позволяют находить способы и условия их оптимального использования, конструировать алгоритмы выполнения немодульных операций, и давать сравнительные оценки алгоритмической и временной сложности Pix вычисления. Рассматриваются методы и алгоритмы сложных немодульных операций, у которых все ранее известные так и новые позиционные форматы для модулярного представления взаимосвязаны. В конце приводится разработанная методика преобразования чисел из позиционного формата в модулярный формат.

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

> сравнение модулярных величин по их значениям;

> определение переполнения за аддитивный и мультипликативный диапазоны;

> деление в модулярной арифметике; расширение диапазона в модулярной арифметике;

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

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

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

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

В приложении приведены численные примеры и листинги программ написанных на языках С++ и CUDA.

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

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

информации

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

Как известно в современном мире потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия "классических" - по схеме фон Неймана - ЭВМ привели к появлению вычислительных систем многоразряд-» ной обработки информации [10]. В свою очередь параллельные вычисления

особую значимость приобрели с переходом компьютерной индустрии на массовый выпуск многоядерных процессоров[16,41,74]. Тенденция роста супервычислений была подхвачена производителями видеокарт, мощности которых возросли настолько, что предопределило их использование не только в графических расчетах, но и в качестве ускорителей вычислений общего назначения. Соответствующие решения представлены в настоящее время компанией NVIDIA и компанией AMD и демонстрируют в силу специфики внутреннего устройства потрясающую (в сравнении с универсальными процессорами) пиковую производительность, превышающую 1терафлопс.

Исследуя множество систем с параллельной архитектурой, рассмотрим подробно способы организации вычислительных процессов в системах с GPU-процессорами компании NVIDIA. Логичность такого выбора заключается в концепции менее затратных разработок процессоров в виду его менее сложной логикой реализации и меньшей тактовой частотой, чем у других процессоров[95,103].

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

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

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

Хост процессор

Блок распределения задач

а а.

a S з a « о § 1 2 f. в о з a ¡1 о в Ё *

= k с $

5 5

Текстурные

модули

Кэш LI

о.

о

_ и « и

§ I

= Z s

в. о

« а

3 а

и 5

о а.

о g

= 5

= и S

Текстурные модули

Кэш L1

ш

«

3 я ¡1

И

с!

S

а о

« й

3 я в Я

§ a

О Е

ё 5 = i

s

Текстурные модули

Кэш L1

т

а

о

в О

¡1 о в

с i

S

а

о

я й

з a

и 3 в 8 a §■

ё 5

с £

>>

S

Текстурные модули

Кэш L1

а

о

>S ы

I I I |

в Ъ С i

5

а о

« U

2 я в Я

в п.

* S-о Е

ё S

= и

S

Текстурные модули

КэшИ

а.

о

« и ~ и

№ И

S I

® I

о Ь

1=

и ш

л w

§ I

= I

® ^

— ^

s

Текстурные модули

Кэш L1

а

0

« и

з a

i| ° 5

ё 5

= к

1

о.

о

« о

з a

1| ь s

° ъ

= 1

7

Текстурные модули

Кэш L1

а

о

_ и

в CJ

з a

II

И = i

S

ш

в

3 ~

и Я

§ I

2 I

о ^

е= ч

Текстурные модули

Кэш L1

ZL

Регистры общего назначения Кэш L2 Регистры общего назначения Кэш L2 Регистры общего назначения Кэш L2

4 I) 4 ) < >

Видеопамяти | | Видеопамять j Видеонамип,

Регистры общего назначе-

Кэш L2

О

Регистры общего назначения Кэш L2

4 |>

Видеопамять |

Регистры общего иазначе-

Кэш L2

Рис. 1.1.1 - Абстрактная схема GPU-процессора

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

■ 16 мультипроцессоров по 8 ядер;

■ 768 МЬ памяти;

■ 128 потоковых унифицированных процессоров, каждый их которых работает на тактовой частоте 1,35 ГГц;

■ Потоковые процессоры сгруппированы в восемь блоков по 16 штук, каждый из которых оснащен четырьмя текстурными модулями и общим L1-кэшем;

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

Обзорный анализ показывает, что 128 простых потоковых процессоров могут работать на частоте около 1.5 ГГц. Такие характеристики обеспечивают быстродействие на уровне 1,9 трлн. операций с плавающей запятой в секунду. Это даёт основания утверждать, что представленная выше архитектура позволяет создавать суперкомпьютеры, которые по своей производительности в десятки раз быстрее существующих ныне.

Характеристики GPU - процессора представлены в таблице 1.1.1.

Таблица 1.1.1-Технические характеристики процессоров NVIDIA.

NVIDIA GeForce

Наименование технических характеристик 8800

Графический процессор G80 (TSMC)

Число транзисторов, млн. 0.09 (low-k)

Площадь ядра, кв.мм 681

Частота графического процессора, МГц 484

Эффективная частота работы видеопамяти, МГц 500

Объем памяти, Мб 1600

Разрядность шины обмена с памятью, Бит 320

Число унифицированных шейдерных процессоров, шт. 96

Частота работы шейдерного блока, МГц 1200

Число текстурных блоков, шт. 24

Число блоков растеризации (ЛОР'в), шт. 20

Полоса пропускания видеопамяти, Гб/сек -64

Теоретическая максимальная скорость выборки текстур, Гтекс./сек -12.0

Требования к мощности блока питания, Ватт ~ 106.0

Размеры видеокарты эталонного дизайна, мм (Д х В х Т) 228 x 100 x 39

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

1) Снижение тактовой частоты.

2) Снижение энергопотребления.

3) Нет ощутимого геометрического роста архитектуры.

4) Экономическая выгода.

—128

---256 ядер ---512 ядер

4» М

О о №

И

о

0 «Л »и

а

5

а

ь ев

s № В X

4>

1

В

S

>>

я

г

а< PQ

3000

2500

2000

1500

1000

500

/

/

Г

/

/

/

____/

г

Г

г~

/

/

г

/

__/

/

31 155 279 403 527 651 775 899 1023

Разрядность мантиссы в битах

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

Список литературы диссертационного исследования кандидат наук Чернобровкин, Виталий Викторович, 2015 год

Список литературы

1. Акритас А. Основы компьютерной алгебры с приложениями: пер. с англ. М. Мир, 1994. 544 с.

2. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. М.: Советское радио, 1968. 440 с.

3. Амербаев В. М., Пак И. Т. Модулярной арифметике - 50 лет // «50 лет модулярной арифметике». Юбилейная Международная научно- техническая конференция (В рамках V Международной научно- технической конференции "Электроника и информатика - 2005"): сб. науч. тр. (23-25 ноября 2005). 2006. С. 5-21.

4. Амербаев В. М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. 324 с.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.

6. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов -М: Издательство «Мир» 1989 г.

7. Балака Е.С., Исследование и разработка сбоеустойчевых устройств бимо-дульной модулярной арифметики: диссерт. на соиск. ученой степени канд. техн. наук. М. 2014, С. 67-71.

8. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003. 328с.

9. Велигоша А. В., Великих С. А. Корректирующие особенности кодов СОК // Тематический сборник ВИПС. 1995. С. 37-38.

Ю.Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХФ-Петербург, 2002. 608 с.

П.Волков Е. А. Численные методы: учеб.пособие для вузов. М.: Лань, 2004. 248 с.

12.Галушкин А. И., Червяков Н. И. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. 270 с.

13.Гашков С. В., Чубариков В. И. Арифметика. Алгоритмы. Сложность вычислений: учеб.пособие для вузов. М.: Высшая школа, 2000. 320 с.

14.Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем. Нижний Новгород.: Издательство Нижегородского госуниверситета, 2010. 18 с.

15.Грегори Р., Кришномурти Е. Безошибочные вычисления. Методы и приложения. М.: Мир, 1988. 207 с.

16.Гук М. Процессоры Intel. П.: Питер, 1997. 224 с.

17.Дадаев Ю. Г. Арифметические коды, исправляющие ошибки. М.: Советское радио, 1968. 168 с.

18.Дженкинс У. К., Этцель X. Особые свойства дополнительных кодов для избыточных систем остаточных классов // ТИИЭР. 1986. Т. 69. № 1. С. 150-151.

19.Дзегеленок И. И., Оцоков Ш. А. Метод ускорения модулярной арифметики с самоисключением ошибок округления // «50 лет модулярной арифметике». Юбилейная Международная научно- техническая конференция (В рамках V Международной научно- технической конференции "Электроника и информатика - 2005") : сб. науч. тр. (23-25 ноября 2005). 2006. С. 362-368.

20.Инютин С. А. Модулярные вычисления в сверхбольших компьютерных диапазонах//Известия вузов. Электроника. 2001. №6. С. 34-39.

21.Инютин С. А. Модулярные вычисления для задач большой алгоритмической сложности // «50 лет модулярной арифметике». Юбилейная Международная научно-техническая конференция (В рамках V Международной

научно-технической конференции "Электроника и информатика - 2005") : сб. науч. тр. (23-25 ноября 2005). 2006. С. 218-224.

22.Инютин С. А. Теория и методы моделирования вычислительных структур с параллелизмом машинных операций: диссерт. на соиск. ученой степени д-ра техн. наук. М., 2001. 5 - 264 с.

23.Каппелини А., Константинидис Дж., Эмелиани П. Цифровые фильтры и их применение: пер. с англ. М. : Энерго-атомиздат, 1983. 360 с.

24.Карацуба А. А., Офман Ю. П. Умножение многоразрядных чисел на автоматах // ДАН СССР. 1961. Т. 145 (2). С. 293-294.

25.Каханер Д., Моулер К., Кэш С. Численные методы и программное обеспечение. М.: Мир, 2001. 575 с.

26.Клеллан Дж. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1985. 234 с.

27.Клязник В. В., Ласкеев С. Н. Применение системы остаточных классов для построения цифровых фильтров // Вычислительные средства в технике и системах связи. 1978. №3. С. 75-80.

28.Кнут Д. Искусство программирования. Получисленные алгоритмы. М. и др.: Вильяме, 2004. Ч. 2. 828 с.

29.Коляда А. А. Модулярные структуры конвейерной экспресс-обработки цифровой информации в измерительно-вычислительных системах физического эксперимента: диссерт. на соиск. ученой степени д-ра техн. наук. Минск, 1991.

30.Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации. Минск: Университетское, 1992. 256с.

31.Коляда А. А., Чернявский А. Ф. Модулярные вычислительные структуры: Вчера, Сегодня, Завтра // «50 лет модулярной арифметике». Юбилейная Международная научно-техническая конференция (В рамках V Международной научно-технической конференции "Электроника и информатика - 2005"): сб. науч. тр. (23-25 ноября 2005). 2006. С. 23-34.

32.Копыткова Л. Б. Математические модели нейросетевой реализации модулярных вычислительных структур для высокоскоростной цифровой фильтрации: диссерт. на соиск. ученой степени канд. физ.- мат. наук. Ставрополь, 2001. 264 с.

33.Копыткова Л. Б., Сахнюк П. А. Адекватность математических моделей модулярной арифметики и нейроподобной сети // Математическое моделирование в научных исследованиях: Материалы Российской научной конференции (27-30 сентября 2000). Ставрополь: Изд-во СГУ, 2000.4.11. С. 187-191.

34.Лавриненко И. Н. Деление чисел, представленных в системе остаточных классов // Инфокоммуникационные технологии. 2005. Т. 3. №3. С. 6-9.

35.Лавриненко И. Н. Разработка математических методов моделирования модулярного нейропроцессора цифровой обработки сигналов: диссерт. на соиск. ученой степени канд. физ.-мат. наук. Ставрополь, 2005. 207 с.

36.Лобес М. В. Направления усовершенствования высокопроизводительных ЭВМ // Физико-математические науки на современном этапе развития Ставропольского государственного университета: Материалы 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (3-24 апреля 2006). Ставрополь, 2006. С. 108-111.

37.Лобес М. В. Непозиционные системы счисления и вычислительные структуры с параллельным представлением и обработкой информации// XIV Туполевские чтения: Материалы международной молодежной научной конференции (10-11 ноября 2006), Казань, 2006. Т. IV. С. 21-23.

38.Лобес М. В. Об одном недостатке системы остаточных классов и методах его преодоления // XIV Туполевские чтения: Материалы международной молодежной научной конференции (10-11 ноября 2006). Казань, 2006. Т. IV. С. 18-20.

39.Лобес М. В. О возможности реализации вычислительной модели системы остаточных классов в нейросетевом логическом базисе // Труды участии-

ков Международной школы-семинара по геометрии и анализу памяти Н.В.Ефимова (5-11 сентября 2006). Ростов-на-Дону, 2006. С. 210-212.

40.Малашевич Д. Б. Недвоичные системы в вычислительной технике // «50 лет модулярной арифметике». Юбилейная Международная научно- техническая конференция (В рамках V Международной научно- технической конференции "Электроника и информатика — 2005") : сб. науч. тр. (23-25 ноября 2005). М., 2006. С. 599-613.

41.Марковский А. Д. Структура вычислительных систем с точки зрения точности и алгебраических критериев качества вычислений: диссерт. на со-иск. ученой степени канд. техн. наук. М., 1979.

42.Михлин С. Г. Некоторые вопросы теории погрешностей. Л. : Изд-во Ленинградского университета, 1988. 333 с.

43.Ноден П., Ките К. Алгебраическая алгоритмика (с упражнениями и решениями): пер. с фр. М.: Мир, 2009. 720 с.

44,Оцоков Ш. А. Алгоритмическая и структурная организация высокопроизводительных ЭВМ с использованием модели безошибочных вычислений : диссерт. на соиск. ученой степени канд. техн. наук. М., 2003.

45.0цоков Ш. А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений // Нейрокомпьютеры: разработка, применение. 2004. №12. с. 33-34.

46.0цоков Ш. А. Об ускорении операции сложения чисел с плавающей точкой на основе модулярной арифметики // «50 лет модулярной арифметике». Юбилейная Международная научно-техническая конференция (В рамках V Международной научно-технической конференции "Электроника и информатика - 2005"): сб. науч. тр. (23- 25 ноября 2005). 2006. С. 328-335.

47.0цоков Ш. А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений // Нейрокомпьютеры: разработка и применение. 2004. №12. с. 31-32.

48.Прахар К. Распределение простых чисел. М.: Мир, 1977. 134 с.

49.Саломаа А. Криптография с открытым ключом: пер. с англ. М.: Мир, 2006.304 с.

50.Сахнюк П. А., Шапошников А. В., Копыткова JI. Б. Приближение нейронных сетей и системы остаточных классов для обеспечения отказоустойчивости вычислительных систем // Сборник научных трудов. Физика. Химия. Ставрополь : Изд-во Сев.-Кав. ГТУ, 2010. Вып. 7. С. 101-104.

51.Свобода А. Развитие вычислительной техники в Чехословакии. Система остаточных классов (СОК) // Кибернетический сборник. 1964. Вып. 8. С. 115-148.

52.Сандэрс Д., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров, пер. с англ. М.: ДМК Пресс, 2011. С. 33-40.

53.Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986. С. 288.

54.Тоом A. JI. О сложности схемы из функциональных элементов, реализующей умножение целых чисел // ДАН СССР. 1963. Т. 150 (3). С. 496-498.

55.Торгашев В. А. Система остаточных классов и надёжность ЦВМ. М.: Советское радио, 1973. С. 120.

56.Турчак JI. И., Плотников П. В. Основы численных методов. М.: Физмат-лит, 2002. 300 с.

57.Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений : пер. с англ. М. : Мир, 2011. 280с.

58.Червяков Н. И., Кондратов А. В., Лавриненко С. В. Параллельный метод масштабирования модулярных чисел // Нейрокомпьютеры: разработка, применение. 2007, №5. С. 12-20.

59.Червяков Н. И., Копыткова Л. Б., Непретимова E.H., Сахнюк П. А., Шапошников А. В. Нейрокомпьютеры в системах обработки сигналов. Коллективная монография. М. : Радиотехника, 2003. 272 с.

бО.Червяков Н. И., Копыткова Л. Б., Непретимова Е. Н., Хатамова М. X. Организация микропроцессорных обменов в естественно-надёжных специализированных распределенных вычислительных системах // Вестник Ставропольского государственного университета. 1999. Вып. 20. С. 61-71. 61.Червяков Н. И., Копыткова Л. Б., Непретимова Е. Н., Хатамова М. X. Применение вычетов для представления и обработке данных // Вестник Ставропольского государственного университета. 1999. Вып. 18. С. 64- 72 62.Червяков Н. И., Лавриненко И. Н., Лавриненко С. В., Мезенцева О. С. Методы и алгоритмы округления, масштабирования и деления чисел в модулярной арифметике // «50 лет модулярной арифметике». Юбилейная Международная научно-техническая конференция (В рамках V Международной научно-технической конференции "Электроника и информатика— 2005") : сб. науч. тр. (23-25 ноября 2005). 2006. С. 291-310. 63.Червяков К. И., Лобес М. В. Алгоритм целочисленного деления в системе остаточных классов // Инфокоммуникационные технологии. 2007. Том 5. №4. С. 8-13.

64.Червяков К. И., Лобес М. В. Аппроксимация функций на основе методов безошибочных вычислений в системе остаточных классов // Вести. Ставропольского гос. ун-та. Физико-математические науки. 2005. Вып. 43. С. 5-7.

65.Червяков К. И., Лобес М. В. Модульное возведение в степень // Инфокоммуникационные технологии в науке, производстве и образовании : Третья международная научно-техническая конференция (1-5 мая 2008). Ставрополь: изд-во СевКавГТУ, 2008. Ч. Ш. С. 204-210. бб.Червяков Н. И. Методы и принципы построения модулярных нейрокомпьютеров // «50 лет модулярной арифметике». Юбилейная Международная научно-техническая конференция (В рамках V Международной научно-технической конференции "Электроника и информатика - 2005") : сб. науч. тр. (23-25 ноября 2005). 2006. С. 291- 310.

67.Червяков Н. И. Методы масштабирования модулярных чисел, используемые при цифровой обработке сигналов // Инфокоммуникационные технологии. 2006. Т.4. №3. С. 15-23.

68.Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Нейрокомпьютеры в остаточных классах: учеб.пособие для вузов. М.: Радиотехника, 2003. 272 с.

69.Червяков Н. И., Сахнюк П. А., Шапошников А. В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М.: Физматлит, 2002. 288 с.

70.Червяков Н. И., Тынчеров К. Т., Велигоша А. В. Высокоскоростная обработка сигналов с использованием непозиционной арифметики // Радиотехника. 1997. № 10. С. 23-27.

71.Чернявский А. Ф., Данилевич В. В., Коляда А. А., Селянинов М. Ю. Высокоскоростные методы и системы цифровой обработки информации. Мн.: Белгосуниверситет, 1996. 376 с.

72.Adleman L., Pomerance С, Rumely R. S. On distinguishing prime numbers from composite numbers // Ann. Math. 1988. Vol. 117. P. 173-206.

73.Banerji D. K., Cheung T. Y., Ganesan V. A high-speed division method in residue arithmetic // Proc. 5-th. Symp. on Computer Arithmetic. 1981. P. 158-164.

74.Bayoumi M. A., Jullien G. A., Miller W. С Highly parallel architectures for DSP algorithmus using RNS // Proc. IEEE Jnt. Symp. Circuits and Syst. (5-7 June 1985). New-York, 1985. Vol. 3. P. 1395-1398.

75.Bayoumi M. A. VLSI PLA. Structures for residue number systems arithmetic implementation // Proc. IEEE Jnt. Symp. Circuits and Syst. (4-7 May 1987). New-York, 1987. Vol. 1. P. 132-135.

76.Bosselaerts A., Govaerts R., Vandewalle J. Comparison of three modular reduction functions // Advances in Cryptology — Crypto'93 ; Douglas R. Stinson, editor. Berlin : Springer-Verlag, 1993. Vol. 773. P. 175-186.

77.Brassard G., Monet S., Zuffelato D. Algorithmes pour I'arithmetique des tres grands entiers // Techniques and Science Infomiatique. 1986. Vol. 5. P. 89-102.

78.Chren W. A. A new residue number system division algorithm // Computers Math. Appl. 1990. Vol. 19. P. 13-29.

79.Comba P. G. Experiments in fast multiplication of integers // Technical Report G320-2158, IBM. Cambridge Scientific Center, 1989.

80.Davida G. I., Litov B. Fast parallel arithmetic via modular representation // SIAM J. Comput. 1991. Vol. 20. P. 756-765.

81.Elkenbracht-Huizing M. An implementation of the number field sieve // Experimental Mathematics. 1996. Vol. 5. P. 231-253.

82.Estevez P. F., Paugam M. E., Puzenat D., Ugaite M. A scalable parallel algorithm for training a hierarchical mixture of neural experts // Parallel Comput. 2002. №6. P. 861-891.

83.Koblitz N. Algebraic aspects of cryptography. Springer-Verlag, 1998.

84.Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The number field sieve //Proc. 22-th. ACM Symposium on Theory of Computing. 1990. P. 564-572.

85.Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing, Inc. 1994(2th edition, 2003).

86.Miller, G., Teng, S., Thurston, W., Vavasis, S. Automatic mesh partitioning. -In A. George, John R. Gilbert, and J. Liu, editors, Sparse Matrix Computations: Graph Theory Issues and Algorithms. IMA Volumes in Mathematics and its applications. Springer-Verlag, 1993.

87.Mockus J. et al. Bayesian Heuristic Approach to Discrete and Global Optimization: Algorithms, Visualization, Software, and Applications. Kluwer Academic Publishers, Dordrecht, 1996.

88.Nour-Omid, B., Raefsky, A., Lyzenga, G. Solving finite element equations on concurrent computers. - In A. K. Noor, editor, American Soc. Mech. P. 291-307, 1986. Orton G. A., Peppard L. E., Tovares S. E. New fault tolerant techniques for residue number systems // IEEE Trans. Comput. 1992. Vol. CAS-41 (11). P. 1453-1464.

89.Patterson, D.A., Hennessy J.L. Computer Architecture: A Quantitative Approach. 2d ed. -San Francisco: Morgan Kaufmann., 1996.

90.Pilkington, J., Baden, S. Partitioning with spacefilling curves. Technical Report CS94-349, Dept. of Computer Science and Engineering, Univ. of California, 1994.

91.Pothen, A. Graph partitioning algorithms with applications to scientific computing. - In D. Keyes, A. Sameh, and V. Venkatakrishnan, editors, Parallel Numerical Algorithms. KluwerAcademic Press, 1996.

92.Quinn M.J. Parallel Programming in C with MPI and OpenMP. - New York, NY: McGraw-Hill, 2004.

93.Raghavan, P. Parallel ordering using edge contraction. Technical Report CS-95-293, Department of Computer Science, University of Tennessee, 1995.

94.Roosta, S.H. Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-Verlag, NY.2000.

95.Schloegel K., Karypis G., Kumar V. Graph Partitioning for High Performance ScientificSimulations. 2000.

96.Sterling, T. Beowulf Cluster Computing with Windows. - Cambridge, MA: The MIT Press.,(Ed.) 2001.

97.Strongin R.G., Sergeev Ya.D. Global multidimensional optimization on parallel computer//Parallel Computing, 1992. V. 18. № 11. P.1259-1273.

98.Szabo N., Tanaka R. Residue arithmetic and its applications to computer technology. New-York, 1967.

99.Walshaw, C., Cross, M. Parallel optimization algorithms for multilevel mesh partitioning. Technical Report 99/IM/44, University of Greenwich, London, UK, 1999.

100. Wilkinson B., Allen M. Parallel programming. - Prentice Hall, 1999/

101. Xu, Z., Hwang, K. Scalable Parallel Computing Technology, Architecture, Programming. McGraw-Hill, Boston. 1998.

102. Zomaya, A.Y. (Ed.) Parallel and Distributed Computing Handbook. -McGraw-Hill, 1996.

Компьютерные модели для многоядерного процессора перевода чисел из

ОПСС в МСС на языке С++

#include <iostream> #include <fstream> #include <cmath> #include <ctime> using namespace std; void M_del8(void); void M_dell6(void); void M_del32(void); void M_Ponizh_Razr8(void); void M_Ponizh_Razrl6(void); void M_Ponizh_Razr32(void); void M_Gorner8(void); void M_Gornerl6(void); void M_Gorner32(void); void M_Poliad8(void); void M_Poliadl6(void); void M_Poliad32(void); clock_t timer(void (*)(void)); int main()

ofstream output("time.txt",ios:rout);

output«"M_del_8 r "«timer (M_del8) «

output«"M_del_16: "«timer (M_del 16) « output«"M_del_32: "«timer (M_del32) « output«"M_Mod_Sum_8: "«timer (M_Ponizh_Razr8) « " output«"M Mod Sum 16r "«timer (M Ponizh Razrl6) «

" ns"«endl;

" ns"«endl; " ns"«endl«endl;

ns"«endl; " ns"«endl;

output«"M_Mod_Sum_32: "«timer (M_Ponizh_Razr32) « " ns "<<endl«endl;

output«"M_Ponizh_Razr_8: "«timer (M_Ponizh_Razr8)/3«" ns"«endl; output«"M_Ponizh_Razr_16: "«timer {M_Ponizh_Razrl6) /4«" ns"«endl;

output«"M_Ponizh_Razr_32: "«timer (M_Ponizh_Razr32)/5«" ns"«endl;

"«timer {M_Gorner8) « " "«timer {M_Gornerl6) « "«timer (M_Gorner32) « "«timer (M_Poliad8) « " output«"M_Poliad_l6: "«timer (M_Poliadl6) « output«"M_Poliad_32: "«timer (M_Poliad32) « output.close();

return 0; }

clock_t timer(void {*FuncPtr)(void)) {

clock_t start,end; start=clock();

for(long i=0; i<pow(10,6); i++

output«"M_Gorner_8: output«"M_Gorner_16: output«"M_Gorner_32: output«"M Poliad 8:

ns"«endl; " ns"«endl; " ns"«endl«endl; ns"«endl; " ns"«endl; " ns"«endl;

(*FuncPtr) 0;

end=clock();

return end-start; }

void M_del8(void) {

const int s=3;

const int A_v[s]={03, 07, 07) ; const int n=3; const int p[n]={03,07,015); // поток входных данных: constintw_v[]={0100, 010, 01); int A = 0;

for (int i=s-l; i>=0; i—)

A=A+A_v[i] *w_v[i] ; //А подается на все нитиП потока //инициализация весовых коэффициентов нитейИпотока floatw2[п]; for (i=0; i<n; i++)

w2[i]=ceil(pow(p[i],-1)*pow(10,4))/pow(10,4); //значения на входе нитей III потока (выходе нитей II потока)

int q[n] ;

for{i=0; i<n; i++)

q[i]=floor(A*w2[ i ] ) ;

//инициализация весовых коэффициентов нитей III потока int w3[n]; for(i=0; i<n; i++) w3[i]= - p[i];

//представление числа А в MCC for(i=0; i<n; i++)

q[i]=A+q[i]*w3[i]; }

void M_dell6(void) {

const int s=6;

const int A_v[s] = {1,1,1,1,1,1}; const int n=4;

const int p[n] = {07,015,035,037}; //данные входного слоя:

constintw_v[]=(0100000, 010000, 01000, 0100, 010, 01}; int A = 0;

for (int i=s-l; i>=0; i—)

A=A+A_v [i] *w_v [i] ; //А подается на все нитиП потока //инициализация весовых коэффициентов нитейИ потока floatw2[п]; for (i=0; i<n; i++)

w2[i]=ceil(pow(p[i],-1)*pow(10,4))/pow(10,4); //значения на входе нитейШ потока (выходе нитейИпотока) int q[п} ; for(i=0; i<n; i++)

q[i]=floor(A*w2[i]);

//инициализация весовых коэффициентов нитейШ входного потока

int w3[n];

for (i=0; i<n; i++)

w3[i]=-p[i] ;

//представление числа А в MCC for(i=0; i<n; i++)

q[i]=A+q[i]*w3[i] ; }

void M_del32(void) {

constint s=ll;

const int A_v[s] = {03, 07, 07, 07, 07, 07, 07, 07, 07, 07, 07 } ; const int n=7;

const int p[n]={07,015,027,035,037,073,075}; //нейрон входного слоя: constint *

w_v[]={010000000000, 01000000000, 0100000000, 010000000, 01000000, 0100000,010000,01000,0100,010,01}; int A = 0;

for (int i=s-l; i>=0; i—)

A=A+A_v [i] *w_v [i] ; //А подается на все нитиИ потока //инициализация весовых коэффициентов нитейИ слоя floatw2[п]; for (i=0; i<n; i++)

w2[i]=ceil(pow(p[i],-1)*pow(10,4))/pow(10,4);

//значения на входе нитейШ. потока (выходе нитейИ потока)

int q[n];

for(i=0; i<n; i++) q[i]=floor(A*w2[i]) ;

//инициализация весовых коэффициентов нитейШ потока intw3[п];

for(i=0; i<n; i++) w3[i]=-p[i];

//представление числа А в MCC for(i=0; i<n; i++)

q[i]=A+q[i]*w3[i ] ; }

void M_Ponizh_Razr8(void) {

const int s=3;

const int A[s]={03,07,07};

const int n=3;

const int p[n]={03,07,015};

//веса II слоя

const int w2[n][s]={{01, 02, 01}, {01, 01, 01}, {014, 010, 01}}; //вычисление вычетов q[i] int q[n]={0};

for(int i=0; i<n; i++) for(int j=0; j<s; j++)

q[i]=(q[i]+A[j]*w2[i] [j] )%p[i] ; {

void M_Ponizh_Razrl6(void) {

const int s=6;

const int A[s] = {1,1,1,1,1,1}; const int n=4;

const int p[n] = {07,015,035,037}; //веса II слоя

const int w2[n][s]= {{01, 01, 01, 01, 01, 01},

{010, 01, 05, 014, 010, 01}, {033, 07, 023, 06, 010, 01}, {01, 04, 020, 02, 010, 01}}; //вычислениевычетов q[i] int q[n]={0}; for(int i=0; i<n; i++) for(int j=0; j<s; j++)

q[i] = (q[i]+A[j]*w2[i] [j] )%p[i];

}

void M_Ponizh_Razr32(void) {

constint s=ll;

const int A[s] = {03,07,07,07,07,07,07,07,07,07,07}; const int n=7;

const int p[n]={07,015,027,035,037,073,075}; //весаИвходногопотока

constintw2[n}[s]= {{01, 01, 01, 01, 01, 01, 01, 01, 01, 01, 01}, {014, 010, 01, 05, 014, 010, 01, 05, 014, 010,01} {03, Oil, 04, 014, 015, 020, 02, 06, 022,010,01}, {04, 017, 024, 021, 015, 033, 07, 023,06,010, 01} {01, 04, 020, 02, 010, 01, 04, 020, 02, 010, 01}, {071, 054, 043, 070, 07,027,031,050, 05, 010, 01} {074,046,024,041,033, 013, Oil, 030, 03, 010,01}} //вычислениевычетовд[i] int q[n]={0}; for(int i=0; i<n; i++) for(int j=0; j<s; j++)

q[i]=(q[i]+A[j]*w2[i] [j])%p[i];

}

void M_Gorner8(void) {

const int s=3;

const int A[s]={03,07,07};

const int n=3;

const int p[n]={03,07,015};

intq[n]={0};

//вычислениеBbraeTOBqfi] . for (int i=0; i<n; i++) for (int j=0; j<s; j++)

q[i]=(q[i]*8+A [j]) %p [i];

void M_Gornerl6(void) {

const int s=6;

const int A[s] = {1,1,1,1,1,1]; const int n=4;

const int p[n] = {07,015,035,037}; intq[n]={0};

//вычисление вычетов q[i] for (int i=0; i<n; i++) for (int j=0; j<s; j++)

q[i]=(q[i]*8+A [j]) %p [i];

}

void M_Gorner32(void) {

constint s=ll;

const int A[s] = {03,07,07,07, 07,07,07, 07, 07,07 const int n=7;

const int p[n]={07,015,027,035,037,073,075}; intq[n]={0};

//вычисление вычетов q[i] for (int i=0; i<n; i++) for (int j=0; j<s; j++)

q[i]=(q[i]*8+A [j]) %p [i];

}

void M_Poliad8(void) {

const int s=3;

const int A[s]={00,01,014};

const int n=3;

const int p[n]={03,07,015};

//веса II слоя

const int Q[n][n]={{01,00,00},

{01,03,00),

{01,03,010});

int q[n]={0};

//вычисление вычетов q[i]

for(int i=0; i<n; i++)

for(int j=0; j<=i; j++)

q[i]=(q[i]+A[j]*Q[i] [j]) %p [i]

}

void M_Poliadl6(void) {

const int s=4;

const int A[s]={01,02,030,030}; const int n=4;

const int p[n] = {07,015,035,037}; //веса II потока

const int Q[n][n]={{01,00,00,00}, {01,07,00,00}, {01,07,04,00}, {01,07,035,04}};

int q[n]={0}; //вычисление вычетов q[i] for(int i=0; i<n; i++) for(int j=0; j<=i; j++)

q[i] = (q[i]+A[j]*Q[i] [j]) %p [

}

void M Poliad32(void) {

const int s=7;

const int A[s]={03,012,020, 026, 022, 050, 046) const int n=7;

const int p[n] = {07, 015, 027, 035, 037, 073, 075) //веса II слоя const int Q[n][n]={{01,00,00,00,00,00,00},

{01,07,00,00,00,00,00}, {01,07,026,00,00,00,00}, {01,07,04,05, 00, 00, 00} , {01,07,035,020,036,00,00}, {01,07,040,034,055,04 6,00}, {01,07,036,023,02,01,073}};

int q[n3={0}; //вычисление вычетов q[i] for(int i=0; i<n; i++) for (int j=0; j<=i; j++)

q[i]=(q[i]+A[j]*Q[i] [j]) %p [i];

}

Компьютерные модели для многоядерного процессора перевода чисел из

МСС в ПСС на языке С++

#include <stdlib.h> #include <stdio.h>

//МСС - модулярная система счисления (непозиционная)

//PSS - позиционная система счисления

void C0K_PSS8(void);

void C0K_PSS16(void);

void COK_PSS32(void);

int main() {

const int s = 3;

int A[s] = {2, 3, 1}; // переводимое число const int n = 3;

const int p[n] = {3, 5, 7}; // система модулей int a[n];

a[0] = A[0];

for(int i = 0; i < n - 1; i++) {

for(int j = i + 1; j < n; j++) {

Aij] -= a[i]; int k = 0;

while( (A[j] + k * p[j]) % p[i] != 0 ) {

k++ ;

}

A[j] = (A [ j ] + k * p[j]) / p [i] ;

}

a [ i + 1] = A [ i + 1 ] ;

}

int sum = 0; int mul = 0; int j = 0;

for(int i = 0; i < n; i++) {

mul = a[i] ; j = i;

while(j > 0) {

mul = mul * p[j - 1]; j — ;

}

эглп = sum + mul;

}

printf("%d\n", sum); return 0;

}

void MCC_PSS8(void) {

const int s = 3;

int A[s] = {00, 03, 010} ;

const int n = 3;

const int p[n] = {03, 07, 015};

int a[n];

a[0] = A[0];

for(int i = 0; i < n - 1; i++) {

for(int j = i + 1; j < n; j++) {

A [ j ] -= a [i] ; int k = 0;

while ( ( A[j] + k * p[j] ) % p[i] {

k++ ;

}

A[j] = (At j ] + k * p[j]) / p [ i ];

}

a[i + 1] = A[i + 1] ;

}

}

void MCC_PSS16(void) {

const int s = 4;

int A[s] = {01, 02, 030, 01};

const int n = 4;

const int p[n] = {07, 015, 035, 037}; int a[n];

a [0] = A[0] ;

for(int i = 0; i < n - 1; i++) {

for(int j = i + 1; j < n; j++) {

A[j] -= a [i] ; int k = 0;

while ( (A[ j ] + k * p[j]) % p[i] ! {

k++;

}

A[j] = (A[j] + k * p[j]) / p[i];

}

a [ i + 1] = A [ i + 1 ] ;

}

void MCC_PSS32(void) {

const int s = 7;

int A[s] = {03, 010, 013, 017, 03, 062, 070}; const int n = 7;

const int p[n] = {07, 015, 027, 035, 037, 073, 075}; int a[n];

a[0] = A[0];

for(int i = 0; i < n - 1; i++) » {

for(int j = i + 1; j < n; j++) {

A[j] -= a [ i ] ; int k = 0;

while ( (A [ j ] + k * p[jj) % p[i] ! = 0 ) {

k++;

}

A [ j ] = (A[ j ] + k * p[j]) / p[i];

}

a[i + 1] = A[i + 1] ;

}

}

Операции сложения и умножения с массивами больших размерностей на

языке CUDA

#include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> #include <fstream>

#include <cufft.h> #include <cuda.h> #include <cutil_inline.h>

#include <shrQATest.h> #include <iostream>

using namespace std;

#define SIGNAL_SIZE 8192 #define SIGNAL_COUNT 384 #define RAY_COUNT 512

typedef double Complex;

static _global_ void ComplexMA(Complex* , Complex* , Complex*

) ;

static _global_ void ComplexMA(Complex* masl, Complex* mas2,

Complex* mas_tmp) {

const int numThreadsX = blockDim.x * gridDim.x;

const int threadlDX = blockldx.x * blockDim.x + threa-dldx.x;

const int numThreadsY = blockDim.y * gridDim.y;

const int threadlDY = blockldx.y * blockDim.y + threa-dldx.у;

int j=0, m=0, p=0; Complex c;

for(int m = threadlDY; m <RAY_COUNT; m+= numThreadsY) {

for (int i = threadlDX; i <SIGNAL_COUNT*SIGNAL_SIZE;

i+= numThreadsX) {

j =m* SIGNAL_COUNT+i/(SIGNAL_SIZE); p=m*SIGNAL_SIZE+(i-SIGNAL_SIZE*j)%SIGNAL_SIZE;

c=masl[i]*mas2[j]; mas_tmp[p]+=c;

}

}

int main(int argc, char** argv) {

ofstream file("out.txt"); dim3 dimGrid(6144,16); dim3 dimBlock(512,32); cudaEvent_t start, stop; float elapsedTime; cudaEventCreate(Sstart) ; cudaEventCreate(Sstop) ;

srand(1000); Complex* mas_tmp;

mas_tmp =new Complex [RAY_COUNT*SIGNAL_SIZE];

for(unsigned int i = 0; i <RAYjCOUNT*SIGNAL_SIZE; ++i) mas_tmp[i]=0;

Complex* masl;

masl =new Complex [SIGNAL_COUNT*SIGNAL_SIZE];

for(unsigned int i = 0; i <SIGNAL_COUNT*SIGNAL_SIZE; ++i) {

masl[i] =1;

file«" ["«i«"] "«" ( "«masl [i] «") ; ";

}

file«endl«endl<<endl«endl«endl«endl«endl«endl«endl <<endl«endl«endl<<"-------------------------------------------

"<<endl«endl«endl<<endl«endl<<endl«endl«endl<<endl<<endl«e ndl«endl;

Complex* mas2;

mas2 =new Complex [RAY_COUNT*SIGNAL_COUNT];

for(unsigned int i = 0; i < RAY_COUNT*SIGNAL_COUNT; ++i) {

mas2[i] = 1;

file«" ["«i«"] "«" ("«mas2 [i] «") ;

}

file«endl«endl«endl«endl«endl«endl«endl«endl«endl <<endl<<endl<<endl<<"-------------------------------------------

"<<endl<<endl«endl«endl<<endl<<endl«endl«endl«endl<<endl«e ndl<<endl;

cudaEventRecord(start, 0) ; Complex* mastmp_;

cutilSafeCall(cudaMalloc(&mastmp_, RAY_COUNT*SIGNAL_SIZE*sizeof(Complex))); Complex* masl_;

cutilSafeCall(cudaMalloc(&masl_, SIG-NAL_SIZE*SIGNAL_COUNT*sizeof(Complex))); Complex* mas2_;

cutilSafeCall(cudaMalloc(&mas2_, RAY_COUNT*SIGNAL_COUNT*sizeof(Complex)));

cutilSafeCall(cudaMemcpy(masl_, masl, SIG-NAL_SIZE*SIGNAL_COUNT*sizeof(Complex), cudaMemcpyHostToDevice));

cutilSafeCall(cudaMemcpy(mas2_, mas2, RAY_COUNT-*SIGNAL_COUNT*sizeof (Complex) , cudaMemcpyHostToDevice) ) ;

cutilSafeCall(cudaMemcpy(mastmp_, mas_tmp, RAY_COUNT*SIGNAL_SIZE*sizeof(Complex), cudaMemcpyHostToDevice));

ComplexMA«<dimBlock, dimGrid>>> (masl_, mas2_,mastmp_); cutilCheckMsg("Kernel execution failed [ ComplexMA ]");

cutilSafeCall(cudaMemcpy(mas_tmp, mastmp_,

RAY_COUNT*SIGNAL_SIZE*sizeof(Complex), cudaMemcpyDeviceToHost));

cutilSafeCall(cudaMemcpy(masl, masl_, SIG-NAL_COUNT*SIGNAL_SIZE*sizeof(Complex), cudaMemcpyDeviceToHost));

cudaEventRecord(stop,0); cudaEventSynchronize(stop);

cudaEventElapsedTime(&elapsedTime, start,stop); printf("Time %3.10f ms\n", elapsedTime);

for(unsigned int i = 0; i <RAY_COUNT*SIGNAL_SIZE; ++i) file«" ["«i«"] "«" ("<<mas_tmp [i] «") ; ";

free(masl)/ free(mas2); free(mas_tmp);

cudaEventDestroy(start); cudaEventDestroy(stop);

cutilSafeCall(cudaFree(masl_)); cutilSafeCall(cudaFree(mas2_));

cutilSafeCall(cudaFree(mastmp_));

cutilDeviceReset() ; system ("pause"); return 0;

}

Умножение вектора на число на языке CUDA

//умножение вектора на число

float *vectorbynumber(float number, float *vect) {

float *result;

result = (float *) malloc(NSIZE * sizeof(float)); for (int i = 0; i < NSIZE; i++) { result[i] = 0.0;

}

for (int i = 0; i < NSIZE; i++) { result[i] += number * vectfi];

}

return result;

}