Электронная вычислительная машина с многими потоками команд и одним потоком данных
Изобретение относится к устройству электронных вычислительных машин и может быть использовано в ЭВМ общего назначения для ускорения вычислительного процесса при обработке структурированных данных. Основное отличие предлагаемой ЭВМ от известных заключается в том, что информация обрабатывается одновременно двумя и более потоками команд. Информация, представленная в виде структуры состоит из взаимосвязанной совокупности данных (информационной части) и связей между ними (структурной части). Тогда первый поток команд 6 из оперативной памяти 4 обрабатывает структурную часть потока данных 8, а второй поток команд 5 обрабатывает информационную часть 7 потока данных 8. Для обработки каждого потока команд предлагается использовать отдельное устройство: центральный процессор 1, содержащий кэш-память 9, используется для обработки данных потоком команд 5; структурный процессор 2, содержащий память для хранения структур 3, используется потоком команд обработки структуры 6. Технические результаты, достигаемые при использовании изобретения, выражаются в следующем:
- Повышается количество вычислений в ЭВМ, выполняемых параллельно.
- Ускоряется обработка структурной части информации за счет применения специально спроектированного устройства - структурного процессора.
- Машинный язык ЭВМ приближается к языку программирования высокого уровня, что сокращает время разработки программ и их размер, уменьшает количество ошибок в программах; ускоряет работу программ; уменьшает стоимость программных продуктов.
Электронная вычислительная машина с многими потоками команд -и одним потоком данных.
Изобретение относится к устройству электронных вычислительных машин и может быть использовано в ЭВМ общего назначения для ускорения вычислительного процесса при обработке структурированных данных.
Вычисления в ЭВМ предполагают наличие информации (данных) и указание последовательности действий над ними (команд). По известному способу построения ЭВМ информация и программы сохраняются в оперативной памяти, откуда их извлекает обрабатывающее устройство (процессор) [1 стр.1902, 2 стр.35-38].
Согласно [1 стр. 1902], архитектуру ЭВМ можно классифицировать по количеству потоков команд и данных в ней. В [1 стр.1902] предложены четыре класса ЭВМ: ЭВМ с одним потоком команд и одним потоком данных (ОКОД);
ЭВМ с одним потоком команд и многими потоками данных (ОКМД); ЭВМ с многими потоками команд и одним потоком данных (МКОД); ЭВМ с многими потоками команд и многими потоками данных (МКМД).
ЭВМ с архитектурами ОКОД, ОКМД и МКМД нашли большое применение. Класс ОКОД повсеместно используется в составе более продуктивных вычислительных машин с ОКМД архитектурой, к которым можно отнести векторно-конвейерные вычислительные машины [2 стр.492]. МКМД является более широким классом и может включать ОКМД и ОКОД архитектуры.
К классу МКОД к данному моменту не отнесена ни одна из вычислительных машин [2 стр.491. 3 стр.18]. По устоявшемуся представлению [4 стр.44], не найдены важные вычислительные задачи, требующие создания ЭВМ с такой архитектурой. Можно констатировать, что к классу МКОД относятся лишь отдельные части современной ЭВМ.
По принципу МКОД в частности функционирует конвейер процессора. Это означает, что одна и та же информация проходит несколько стадий конвейера, где над ней производят различные преобразования в соответствии с потоками микрокоманд. Однако, наличие конвейера не позволяет отнести всю ЭВМ к МКОД
классу, так как множественность потоков реализована лишь на уровне микрокоманд. В существующих ЭВМ многие потоки микрокоманд возникают лишь вследствие одного потока команд.
По существующему на данный момент представлению о программах функционирования ЭВМ, совокупность однородной информации представляется в оперативной памяти в одном из двух видов: в виде векторных структур данных (одной и более соседних ячеек оперативной памяти) или в виде списковых структур данных (двух и более любых ячеек оперативной памяти). Разработано несколько десятков структур данных, позволяющих ускорить вычислительный процесс: массивы [5 стр.342], списки [5 стр.295, 6 стр.198], хеш-таблицы [6 стр.215], двоичные деревья поиска [6 стр.236] и другие.
В [7 стр.82, 108] описаны варианты вычислительных алгоритмов, оперирующих графовыми моделями и используемые при автоматизированном проектировании ЭВМ. Основным показателем качества рассмотренных алгоритмов является характер зависимости количества операций сравнения, требуемых для их реализации, от размерности решаемой задачи, т.е. вычислительная сложность. Допустим в программе, обрабатываемой процессором, используется какая либо списковая структура данных (список, сбалансированное дерево и т.д.). В такой структуре отношение смежности элементов задано в виде явных указателей. Известно, что такой принцип позволяет ускорить многие операции со структурой: удаление, добавление, объединение, поиск и др. Этот факт для многих алгоритмов позволяет сократить количество операций процессора, т.е. сокращает вычислительную сложность алгоритма [6 стр.475, 7 стр.112]. Часто оказывается выгодным создавать многоуровневые связанные структуры, такие как: деревья, прошитые списками, многомерные списки и другие. Применение же векторных структур, напротив, ведет к усложнению алгоритмов. Для рассмотренных в [7 стр.82, 108] алгоритмов массивы оказываются сильно разряжены, в связи с чем вычислительная сложность увеличивается до O(n2), но, благодаря представлению всех необходимых действий в виде операций над структурами данных, были получены варианты алгоритмов с теоретическими оценками вычислительной сложности близкими к оптимальным (O(n)).
Результаты экспериментов показывают, что обработка списковых структур данных современными ЭВМ классов ОКОД и ОКМД происходит значительно
медленнее, чем обработка векторных структур [8 стр.158]. Этому способствуют архитектурные особенности существующих ЭВМ (наличие конвейера, кэш-памяти, пакетного режима передачи данных из оперативной памяти в центральный процессор, предвыборка команд и данных и другие). Кроме того, списковые структуры обладают зависимостью по данным, вследствие чего запрос на получение очередной порции информации может быть выдан центральным процессором только после получения предыдущих данных. В современных ЭВМ выполнение действий над структурами данных выполняется с помощью центрального процессора и отсутствуют какие-либо устройства, ускоряющие такую обработку.
В предлагаемой ЭВМ, в отличие от известных, один поток данных представляет собой структурированную информацию, над которой требуется выполнять несколько потоков команд. Согласно [9 стр.50], структура данных состоит из информационной и структурной составляющей. В простейшем случае, первый поток команд содержит только действия для обработки структурной части, а второй поток обрабатывает хранимые в структуре данные. Потоки команд и данных предлагаемой ЭВМ поясняются чертежом.
Технический результат достигается тем, что в устройство электронной вычислительной машины, состоящей из Оперативной памяти 4, последовательно соединенной с Кэш-памятью 9, которая входит в состав Центрального процессора 1, в отличие от известных ЭВМ. вводится дополнительный Структурный процессор 2, соединенный с Оперативной памятью 4 и Кэш-памятью 9, который осуществляет хранение и обработку потока структурированных данных 8 в соответствии с первым потоком команд 6, поступающим в него из Оперативной памяти 4, а также передает на дальнейшую обработку поток неструктурированных данных 7 Центральному процессору 1, который обрабатывает их вторым потоком команд 5. Для этого в набор команд ЭВМ вводятся высокоуровневые команды обработки структурированных данных. Указанное устройство 2 (Структурный процессор) будет обрабатывать только такие команды и обменивается с Центральным процессором 1 уже подготовленными неструктурными данными - скалярами. Примером осуществления такого взаимодействия может служить программа, обрабатывающая древовидную структуру: на некотором шаге требуется найти
минимальное значение ключа во всем дереве и увеличить его в 10 раз. Программа на языке, близком к машинному, будет содержать следующие команды:
Вершина=Дерево.ПоискМИН;
Дерево.ИзменитьЗначение(Вершина,Вершина.Ключ*10);
В указанном примере первая команда приводит к выполнению алгоритма обхода структуры и сравнению ключей для поиска наименьшего. Ключ найденной вершины должен быть увеличен в 10 раз, что может потребовать изменения структуры дерева. Очевидно, что действия по поиску вершины с минимальным ключом и последующее перестроение дерева должен выполнить Структурный процессор 2, а за увеличение значения ключа отвечает арифметико-логическое устройство Центрального процессора 1.
Большинство действий над структурами требует интенсивного обращения к памяти. Использование медленной Оперативной памяти 4 не позволит существенно ускорить обработку и создаст дополнительную нагрузку на системную магистраль между Центральным процессором 1 и Оперативной памятью 4. Поэтому в предлагаемом устройстве ЭВМ вводится локальная Память структур 3, которая содержит только необходимую для Структурного процессора 2 информацию. Загрузка структуры или ее части, а также сохранение содержимого Памяти структур 3 в Оперативную память 4 выполнятся по специализированным алгоритмам, учитывающим тип структуры и форматы хранимых данных. Указанная Память структур 3 построена таким образом, чтобы максимально ускорить действия над ее содержимым Структурному процессору 2.
Обработка данных в предлагаемой ЭВМ осуществляется следующим образом. Поток структурированных данных 8 из Оперативной памяти 4 направляется в Память структур 3. Поток команд для обработки структур данных 6 направляется в Структурный процессор 2. Найденная в структуре или обработанная другим способом информация направляется в Кэш-память 9 и составляет поток скалярных данных 7. Центральный процессор 1 извлекает скалярные данные из Кэш-памяти 9 и обрабатывает их в соответствии с потоком команд обработки скалярных данных 5. Результат работы Центрального процессора 1 направляется обратно в Память структур 3 в потоке скалярных данных 7.
Основное отличие предлагаемой ЭВМ от известных заключается в том, что информация обрабатывается одновременно двумя и более потоками команд.
Информация, представленная в виде структуры состоит из взаимосвязанной совокупности данных (информационной части) и связей между ними (структурной части). Тогда первый поток команд 6 из Оперативной памяти 4 обрабатывает структурную часть потока данных 8, а второй поток команд 5 обрабатывает информационную часть 7 потока данных 8. Для обработки каждого потока команд предлагается использовать отдельное устройство: Центральный процессор 1, содержащий Кэш-память 9, используется для обработки данных потоком команд 5;
Структурный процессор 2, содержащий память для хранения структур 3, используется потоком команд обработки структуры 6.
Электронная вычислительная машина с многими потоками команд и одним потоком данных может быть реализована с помощью полностью заказных или полузаказных СБИС, а также на большеразмерных ПЛИС.
Технические результаты, достигаемые при использовании изобретения, выражаются в следующем:
- Повышается количество вычислений в ЭВМ, выполняемых параллельно.
- Ускоряется обработка структурной части информации за счет применения специально спроектированного устройства -структурного процессора.
- Машинный язык ЭВМ приближается к языку программирования высокого уровня, что сокращает время разработки программ и их размер, уменьшает количество ошибок в программах; ускоряет работу программ; уменьшает стоимость программных продуктов.
Библиографические данные
1. Flynn M.J. "Very High-Speed Computing Systems", Proceedings IEEE, №54, 1966, pp.1901-1909
2. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем: Учебник для вузов. - СПб.: Питер, 2006. - 668 с.: ил.
3. Богданов А.В., Корхов В.В., Мареев В.В., Станкова Е.Н. Архитектура и топологии многопроцессорных вычислительных систем. Курс лекций. Учебное пособие. - М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2004. - 176 с.
4. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. Учебник для вузов. Л.: Энергоатомиздат. Ленингр. Отд-ние, 1987. 288 с.: ил.
5. Кнут Д. Искусство программирования. Т.1.: Основные алгоритмы. 2-е изд.: Пер. с англ. - М.: Издательский дом «Вильяме», 2001. - 720 с.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2000. - 960 с.
7. Попов А.Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ. Дисс. кандидата техн. наук. - М.: 2003. - 176 с.
8. Касперски К. Техника оптимизации программ. Эффективное использование памяти. - СПб.: БХВ - Петербург, 2003. - 464 с.: ил.
9. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах: Учеб. пособ. для вузов. - М.: Высш. шк. 1987. - 248 с.: ил.
Электронная вычислительная машина с многими потоками команд и одним потоком данных, состоящая из оперативной памяти, последовательно соединенной с кэш-памятью, которая входит в состав центрального процессора, отличающаяся тем, что в нее введен дополнительный структурный процессор, содержащий память для хранения структур данных, соединенный с оперативной памятью и кэш-памятью, который осуществляет хранение и обработку потока структурированных данных в соответствии с первым потоком команд, поступающим в него из оперативной памяти, а также передает на дальнейшую обработку поток неструктурированных данных центральному процессору, который обрабатывает их вторым потоком команд, в результате чего в предлагаемой ЭВМ один поток информации в виде структур данных обрабатывается двумя и более потоками команд, где второй и другие потоки команд к центральному процессору приводят к обработке информационной составляющей данных, а первый и другие потоки команд к структурному процессору приводят к обработке структурной составляющей данных.
