ВВЕДЕНИЕ 5
1 АНАЛИЗ КЛАССИЧЕСКИХ МЕТОДОВ ПОВЫШЕНИЯ
ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 7
1.1 Решения проблемы быстродействия 7
1.1.1 Увеличение числа транзисторов на кристалле микросхемы 7
1.1.2 Многоядерные процессоры 10
1.1.3 Графические процессоры 12
1.2 Ассоциативная память как ресурс распределенных вычислений 14
1.3 Отличие от архитектуры фон Неймана 19
1.4 Использование MRAM для реализации ассоциативной памяти 20
1.5 Выводы по разделу один 24
2 ОТОБРАЖЕНИЕ КЛАССИЧЕСКИХ АЛГОРИТМОВ СОРТИРОВКИ НА
АССОЦИАТИВНУЮ ПАМЯТЬ 25
2.1 Быстрая сортировка 26
2.2 Пузырьковая сортировка 29
2.3 Сортировка вставками 33
2.4 Бисерная сортировка 36
2.5 Сортировка выбором 37
2.6 Выводы по разделу два 38
3 РАЗРАБОТКА И ТЕОРЕТИЧЕСКИЙ АНАЛИЗ АЛГОРИТМОВ
СОРТИРОВКИ 40
3.1 Алгоритм сортировки с предварительным группированием 40
3.1.1 Алгоритм 41
3.1.2 Пример использования алгоритма 43
3.2 Алгоритм сортировки с подсчетом единиц 45
3.2.1 Алгоритм 46
3.2.2 Пример использования алгоритма 46
3.3 Выводы по разделу три 49
4 МОДЕЛИРОВАНИЕ АЛГОРИТМОВ СОРТИРОВКИ 50
ЗАКЛЮЧЕНИЕ 54
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Автоматизация производства, совершенствование устройств контроля, хранения, обработки приводят к увеличению объема используемой информации. Люди сталкиваются с проблемой быстрой обработки больших массивов данных. Но информации с каждым днем становится все больше, производители вычислительных и запоминающих устройств зачастую не могут обеспечить требуемой скорости доступа и обработки данных.
Для увеличения производительности вычислительных устройств в настоящее время используется распараллеливание обработки информации. Одним из методов распараллеливания является применение вычислительных устройств на базе SIMD архитектур. Такими архитектурами являются графические процессоры и АП. В настоящей работе осуществляется анализ вычислительных свойств АП.
Отличительной особенностью ассоциативных запоминающих устройств заключается в том, что они способны выдавать хранящуюся в них информацию без предварительного указания адресов тех ячеек, в которых находятся данные. Для поиска информации используется некоторая совокупность свойств или описаний объекта. Также АП позволяет получить параллельный доступ ко всем ячейкам памяти.
На сегодняшний день появилось такое технологическое решение для изготовления АП, как магниторезистивная память (MRAM). MRAM хранит информацию в виде различного сопротивления элементов хранения. Это обеспечивает уменьшение энергопотребления, увеличения срока службы и быстродействия по сравнению с другими видами памяти.
Ассоциативная память (АП) обладает большим потенциалом повышения производительности обработки информации. Но проведено мало исследований по внедрению и возможностям использования данного вида памяти. Этим обуславливается актуальность данной работы.
Вычислительные свойства АП изучены еще недостаточно, поэтому в работе осуществляется анализ одной из наиболее распространенных задач обработки информации - сортировки, как одного из наиболее ресурсозатратных преобразований.
Цель и задачи исследования
Цель научно-исследовательской работы - определить с теоретической точки зрения возможности реализации в АП различных известных алгоритмов сортировки и предложить решения, направленные на повышение алгоритмической производительности с учетом структуры и свойств АП.
Для достижения поставленной цели следует решить следующие задачи:
• исследование и выявление особенностей функционирования ассоциативной памяти;
• анализ существующих разработок АП на магниторезистивной памяти;
• анализ и исследование отображения существующих алгоритмов преобразований на АП;
• формирование новых алгоритмов, учитывая особенности ассоциативно-решающих полей;
• моделирование изученных и разработанных алгоритмов преобразований и их сравнение.
Для выполнения работы был проведен поиск и анализ информации по теме ассоциативной памяти. Поиск осуществлялся по базам данных патентов, диссертаций, научных работ. В результате поиска и анализа выяснилось, что существуют реализации ассоциативной памяти на магниторезистивной памяти. Ассоциативная память обладает большим потенциалом повышения производительности обработки информации. Но проведено мало исследований по внедрению и возможностям использования данного вида памяти.
В настоящей работе представлены исследования по отображению известных алгоритмов сортировки на АП. Рассмотренные алгоритмы недостаточно эффективно используют особенности архитектуры и функционирования АП. Были предложены решения по их модификации. В результате, временная сложность алгоритмов улучшилась в ^ раз (п - количество элементов в сортируемом массиве, т - разрядность).В 3 главе работы представлены новые алгоритмы сортировки. Произведена оценка их быстродействия. Алгоритм сортировки с подсчетом единиц показал наилучший результат. Моделирование разработанных алгоритмов подтвердило теоретические расчеты.
