Реферат: Проектирование машины потоков данных

Содержание:

1.Введение…………………………………………………………………………………………….3

2.Теоретическийраздел………………………………………………………………………………6

2.1. Принцип действия машин потоков данных…………………………………………….6

2.2. Язык потоков данных…………………………………………………………………….9

2.3. Машина потоков данных………………………………………………………………..13

2.4. Сети трактов передачи пакетов…………………………………………………………16

2.5. Переполнение и тупиковые ситуации………………………………………………….20

2.6. Обработка структур данных…………………………………………………………….23

3.Практическаячасть…………………………………………………………………………………28

3.1. Постановка  и  реализация задачи……………………………………………………...28

3.2. Реализация программы на машине потоков данных…………………………………..30

3.3. Принцип работы устройства…………………………………………………………….32

3.4. Спецификация элементов………………………………………………………………..36

4.Заключение………………………………………………………………………………………….38

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

5.Приложения…………………………………………………………………………………………41

ВСГТУ 622-1

Изм.

Лист

№ докум.

Подп.

Дата

Разраб.

Проверил

Литер.

Лист

Листов

 Н.контр

 Утв.

Д 630.1.05.00.039.ПЗ

ВВЕДЕНИЕ

<img src="/cache/referats/24383/image001.gif" v:shapes="_x0000_s3563 _x0000_s2947 _x0000_s2948 _x0000_s2949 _x0000_s2950 _x0000_s2951 _x0000_s2952 _x0000_s2953 _x0000_s2954 _x0000_s2955 _x0000_s2956 _x0000_s2957 _x0000_s2958 _x0000_s2959 _x0000_s2960 _x0000_s2961 _x0000_s2962 _x0000_s2963 _x0000_s2964 _x0000_s2965 _x0000_s2966 _x0000_s2967 _x0000_s2968 _x0000_s2969 _x0000_s2970 _x0000_s2971 _x0000_s2972 _x0000_s2973 _x0000_s2974 _x0000_s2975 _x0000_s2976 _x0000_s2977 _x0000_s2978 _x0000_s2979 _x0000_s2980 _x0000_s2981 _x0000_s2982 _x0000_s2983 _x0000_s2984 _x0000_s2985 _x0000_s2986 _x0000_s2987 _x0000_s2988 _x0000_s2989 _x0000_s2990">


1. Введение

Изм

Лист

№докум

Подпись.

Дата

Лист

4

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image002.gif" v:shapes="_x0000_s2924 _x0000_s2925 _x0000_s2926 _x0000_s2927 _x0000_s2928 _x0000_s2929 _x0000_s2930 _x0000_s2931 _x0000_s2932 _x0000_s2933 _x0000_s2934 _x0000_s2935 _x0000_s2936 _x0000_s2937 _x0000_s2938 _x0000_s2939 _x0000_s2940 _x0000_s2941 _x0000_s2942 _x0000_s2943 _x0000_s2944 _x0000_s2945">

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

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

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

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

Изм

Лист

№докум

Подпись.

Дата

Лист

5

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image003.gif" v:shapes="_x0000_s3541 _x0000_s3542 _x0000_s3543 _x0000_s3544 _x0000_s3545 _x0000_s3546 _x0000_s3547 _x0000_s3548 _x0000_s3549 _x0000_s3550 _x0000_s3551 _x0000_s3552 _x0000_s3553 _x0000_s3554 _x0000_s3555 _x0000_s3556 _x0000_s3557 _x0000_s3558 _x0000_s3559 _x0000_s3560 _x0000_s3561 _x0000_s3562">Второй причиной появления машин потоковданных является недостатки, присущие самой природе современных языковпрограммирования, и осознание того факта, что эти языки отражают в своейструктуре основополагающие принципы архитектуры машин фон Неймана. Так жевнутренняя организация современных машин предполагает использование пассивнойпамяти, процессора, выполняющего операции по изменению содержимого памяти, иустройства управления, воздействующего на процессор с помощью потока следующиходна за другой команд. Понятие «переменная» в языке программирования адекватнопонятию «область пассивной памяти» в машине, понятие «передача управления» вязыке (реализуемая, например, операторами GOTO, IF, DO, CALL) отражает устройство управления исчетчик команд в машине фон Неймана. Подобным же образом понятие «присваивание»является отображением определенной операции процессора (изменение содержимогообласти памяти машины). Использование потока данных для управления машинойпозволило сделать выводы, с которыми согласились и специалисты в области теорииязыков

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

Быстрое развитие компьютерной индустрииопределяет относительность понятия суперЭВМ — то, что десять лет назад можнобыло назвать суперкомпьютером, сегодня под это определение уже не попадает.Например, производительность персональных компьютеров Pentium-3/500MHz,сравнима с производительностью суперкомпьютеров начала 70-х годов, однако посегодняшним меркам суперкомпьютерами не являются ни те, ни другие.

 В любом компьютере все основные параметрытесно связаны. Трудно себе представить универсальный компьютер, имеющий высокоебыстродействие и мизерную оперативную память, либо огромную оперативную памятьи небольшой объем дисков. Следуя логике, делаем вывод: суперЭВМ это компьютеры,имеющие в настоящее время не только максимальную производительность, но имаксимальный объем оперативной и дисковой памяти (вопрос о специализированномПО, с помощью которого можно эффективно всем этим воспользоваться, пока оставимв стороне).

 Так о чем же речь, и какиесуперкомпьютеры существуют в настоящее время в мире? Вот лишь несколькопараметров, дающих достаточно красноречивую характеристику машин этого класса.Компьютер ASCI WHITE, занимающий первое место в списке пятисот самых мощныхкомпьютеров мира, объединяет 8192 процессора Power 3 с общей оперативнойпамятью в 4 терабайта и производительностью более 12 триллионов операций всекунду.

ВСГТУ 622-1

Изм.

Лист

№ докум.

Подп.

Дата

Разраб.

Проверил

Литер.

Лист

Листов

 Н.контр

 Утв.

Д 630.1.05.00.039.ПЗ

ПРИНЦИП ДЕЙСТВИЯ МАШИН ПОТОКОВ ДАННЫХ

<img src="/cache/referats/24383/image004.gif" v:shapes="_x0000_s3564 _x0000_s2992 _x0000_s2993 _x0000_s2994 _x0000_s2995 _x0000_s2996 _x0000_s2997 _x0000_s2998 _x0000_s2999 _x0000_s3000 _x0000_s3001 _x0000_s3002 _x0000_s3003 _x0000_s3004 _x0000_s3005 _x0000_s3006 _x0000_s3007 _x0000_s3008 _x0000_s3009 _x0000_s3010 _x0000_s3011 _x0000_s3012 _x0000_s3013 _x0000_s3014 _x0000_s3015 _x0000_s3016 _x0000_s3017 _x0000_s3018 _x0000_s3019 _x0000_s3020 _x0000_s3021 _x0000_s3022 _x0000_s3023 _x0000_s3024 _x0000_s3025 _x0000_s3026 _x0000_s3027 _x0000_s3028 _x0000_s3029 _x0000_s3030 _x0000_s3031 _x0000_s3032 _x0000_s3033 _x0000_s3034 _x0000_s3035">


2.1. Принцип действия машин потоков данных

Изм

Лист

№докум

Подпись.

Дата

Лист

7

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image005.gif" v:shapes="_x0000_s2923 _x0000_s2895 _x0000_s2896 _x0000_s2897 _x0000_s2898 _x0000_s2899 _x0000_s2900 _x0000_s2901 _x0000_s2902 _x0000_s2903 _x0000_s2904 _x0000_s2905 _x0000_s2906 _x0000_s2907 _x0000_s2908 _x0000_s2909 _x0000_s2910 _x0000_s2911 _x0000_s2912 _x0000_s2915 _x0000_s2916 _x0000_s2917"><img src="/cache/referats/24383/image006.gif" v:shapes="_x0000_s2919">  данныеперемещаются из команды в команду по мере выполнения программы.

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

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

Ор

Ор

Ор

Ор

Ор

<div v:shape="_x0000_s1047"> Команды не готовы к выполнению <img src="/cache/referats/24383/image007.gif" v:shapes="_x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123"> <img src="/cache/referats/24383/image008.gif" v:shapes="_x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130"> <img src="/cache/referats/24383/image009.gif" v:shapes="_x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139"> <div v:shape="_x0000_s1068">

Команда готова к выполнению

<div v:shape="_x0000_s1069">

Результат выполнени<st1:PersonName w:st=«on»>я</st1:PersonName>

<img src="/cache/referats/24383/image010.gif" v:shapes="_x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156"> <img src="/cache/referats/24383/image011.gif" v:shapes="_x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163"> <img src="/cache/referats/24383/image012.gif" v:shapes="_x0000_s1140"> <div v:shape="_x0000_s1070">

Рис. 1. Возможные состо<st1:PersonName w:st=«on»>я</st1:PersonName>ни<st1:PersonName w:st=«on»>я</st1:PersonName> команд в машине потоков данных.


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

Изм

Лист

№докум

Подпись.

Дата

Лист

8

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image013.gif" v:shapes="_x0000_s3565 _x0000_s3566 _x0000_s3567 _x0000_s3568 _x0000_s3569 _x0000_s3570 _x0000_s3571 _x0000_s3572 _x0000_s3573 _x0000_s3574 _x0000_s3575 _x0000_s3576 _x0000_s3577 _x0000_s3578 _x0000_s3579 _x0000_s3580 _x0000_s3581 _x0000_s3582 _x0000_s3583 _x0000_s3584 _x0000_s3585 _x0000_s3586">размножитель, которыйпредставляет собой операцию с одним входом и несколькими выходами. Он готов к работе, когда на входной линии данныеприсутствуют, а выходные линии пустые. Его функции – распределять входныеданные по всем выходным линиям. Размножитель обозначается небольшим зачеркнутымкругом. Вторым новым понятием является бесконечныйисточник констант для команды.

ВСГТУ 622-1

Изм.

Лист

№ докум.

Подп.

Дата

Разраб.

Проверил

Литер.

Лист

Листов

 Н.контр

 Утв.

Д 630.1.05.00.039.ПЗ

ЯЗЫК ПОТОКОВ ДАННЫХ

<img src="/cache/referats/24383/image014.gif" v:shapes="_x0000_s3588 _x0000_s3037 _x0000_s3038 _x0000_s3039 _x0000_s3040 _x0000_s3041 _x0000_s3042 _x0000_s3043 _x0000_s3044 _x0000_s3045 _x0000_s3046 _x0000_s3047 _x0000_s3048 _x0000_s3049 _x0000_s3050 _x0000_s3051 _x0000_s3052 _x0000_s3053 _x0000_s3054 _x0000_s3055 _x0000_s3056 _x0000_s3057 _x0000_s3058 _x0000_s3059 _x0000_s3060 _x0000_s3061 _x0000_s3062 _x0000_s3063 _x0000_s3064 _x0000_s3065 _x0000_s3066 _x0000_s3067 _x0000_s3068 _x0000_s3069 _x0000_s3070 _x0000_s3071 _x0000_s3072 _x0000_s3073 _x0000_s3074 _x0000_s3075 _x0000_s3076 _x0000_s3077 _x0000_s3078 _x0000_s3079 _x0000_s3080">
2.2. Язык потоковданных

Изм

Лист

№докум

Подпись.

Дата

Лист

10

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image015.gif" v:shapes="_x0000_s3081 _x0000_s3082 _x0000_s3083 _x0000_s3084 _x0000_s3085 _x0000_s3086 _x0000_s3087 _x0000_s3088 _x0000_s3089 _x0000_s3090 _x0000_s3091 _x0000_s3092 _x0000_s3093 _x0000_s3094 _x0000_s3095 _x0000_s3096 _x0000_s3097 _x0000_s3098 _x0000_s3099 _x0000_s3100 _x0000_s3101 _x0000_s3102">

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

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

Исполнительный элемент символизируетоперацию, готовую к выполнению при поступлении информации на входные линииэтого элемента и при отсутствии информации на его входных линиях. Существуетдва типа исполнительных элементов – блоки (actor) и размножители (link). Блок – этоисполнительный элемент с одной выходной линией и одной или несколькими входными, размножитель– с одной входной линией и несколькими выходными.

Информация в языкеДенниса представляется в виде токенов, которые передаются по линиям связи,обрабатываются и выдаются исполнительными элементами.

Различаются два вида информации: значениеданных (например, числовые величины) и значения управляющих сигналов (логические величины TRUE – ИСТИННО или FALSE – ЛОЖНО). В описываемомязыке отсутствуют средства для распознавания типов значений данных (целые, сфиксированной точкой, комплексные и т. д.).

Используемые в языке Денниса понятие линия связи (arc)символизирует однонаправленный тракт, по которому информация  передается от одного исполнительного элементак другому. Сигналы на линии связи могут отсутствовать либо на ней можетнаходиться только 1 токен информации. Следовательно, линию связи можнорассматривать как определенный эквивалент традиционных понятий «переменная» и«область памяти».

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

Изм

Лист

№докум

Подпись.

Дата

Лист

11

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image016.gif" v:shapes="_x0000_s3103 _x0000_s3104 _x0000_s3105 _x0000_s3106 _x0000_s3107 _x0000_s3108 _x0000_s3109 _x0000_s3110 _x0000_s3111 _x0000_s3112 _x0000_s3113 _x0000_s3114 _x0000_s3115 _x0000_s3116 _x0000_s3117 _x0000_s3118 _x0000_s3119 _x0000_s3120 _x0000_s3121 _x0000_s3122 _x0000_s3123 _x0000_s3124">


F <img src="/cache/referats/24383/image017.gif" v:shapes="_x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108"><img src="/cache/referats/24383/image018.gif" v:shapes="_x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075">T <img src="/cache/referats/24383/image019.gif" v:shapes="_x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097"><img src="/cache/referats/24383/image020.gif" v:shapes="_x0000_s1081 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080">  

P <img src="/cache/referats/24383/image021.gif" v:shapes="_x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091"> 

f

Блок прин<st1:PersonName w:st=«on»>я</st1:PersonName>ти<st1:PersonName w:st=«on»>я</st1:PersonName> решений

Вентиль Т

<div v:shape="_x0000_s1109">

Размножитель данных

<div v:shape="_x0000_s1111">

Размножитель

<img src="/cache/referats/24383/image022.gif" v:shapes="_x0000_s2560 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086"> <div v:shape="_x0000_s1110">

Блок выполнени<st1:PersonName w:st=«on»>я</st1:PersonName> операций

<img src="/cache/referats/24383/image023.gif" v:shapes="_x0000_s1112 _x0000_s1113"> <div v:shape="_x0000_s1114">

Вентиль F


                                                                                                           

T      F

<img src="/cache/referats/24383/image024.gif" v:shapes="_x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103">


<div v:shape="_x0000_s1116">

Рис. 2. Исполнительные элементы графического <st1:PersonName w:st=«on»>я</st1:PersonName>зыка

<div v:shape="_x0000_s1115">

Смеситель

                                                          

На рис.2. изображены исполнительные элементы языка: сплошные стрелки показывают местаподсоединения линий данных, штриховые – управляющих линий. Операция размноженияготова к выполнению при появлении токена на единственной входной линииразмножителя и при условии, что все его выходные линии пусты. Размножительраспределяет полученный токен по выходным линиям. Блок выполнения операцииобычно имеет одну или две входных линии. Блок готов к работе  при наличии токенов данных на всех еговходных линиях и при условии, что выходная линия пуста. Он принимает входныетокены, выполняет некоторые преобразования над полученными величинами ипомещает результирующий токен данных на свою выходную линию. Типичнымиоперациями таких блоков являются сложение, вычитание, умножение,инвертирование, извлечение квадратного корня и т. д.

Блок принятия решения функционирует аналогичным образом, однакорезультатом его работы является управляющий сигнал (логическая величина). Вэтом блоке вычисляется отношение, составленное из выходных данных,  и формируется в результат в виде логическойвеличины TRUE (ИСТИННО)или FALSE (ЛОЖНО).Типичными операциями отношения являются операции сравнения двух величин поодному из критериев типа «равны», «не равны», «первая величина больше второй» ит. д.

Остальные три блока имеют на входе и данные, и управляющие сигналы. Блок типа вентиль Т (Т – от английскогослова TRUE) готов кработе при наличии на его входах как токена данных, так и токена управляющейинформации (при этом, как обычно, выходная линия должна быть пуста). Как и всеостальные исполнительные элементы,  этотблок  «поглощает» входную информацию вовремя выполнения. Если значение управляющего сигнала TRUE, то имеющийся на входе блока токенданных передается на выходную лини. Если значение управляющего сигнала FALSE, то сигнал на выходеблока не формируется. Таким образом, вентиль T либо пропускает входные данные на свой вход, либо просто«поглощает» их. Блок типа вентиль F (F – отанглийского слова FALSE)работает аналогичным образом, только для передачи токена данных на выходнуюлинию требуется управляющий сигнал, имеющий значение FALSE.

Изм

Лист

№докум

Подпись.

Дата

Лист

12

Д 630.1.05.00.039.ПЗ

<img src="/cache/referats/24383/image025.gif" v:shapes="_x0000_s3589 _x0000_s3590 _x0000_s3591 _x0000_s3592 _x0000_s3593 _x0000_s3594 _x0000_s3595 _x0000_s3596 _x0000_s3597 _x0000_s3598 _x0000_s3599 _x0000_s3600 _x0000_s3601 _x0000_s3602 _x0000_s3603 _x0000_s3604 _x0000_s3605 _x0000_s3606 _x0000_s3607 _x0000_s3608 _x0000_s3609 _x0000_s3610">TRUEи токена данных на линии с меткой Т; 2) одновременное присутствие управляющеготокена FALSE и токенаданных на линии с меткой F.В обоих случаях выходная линия должна быть пуста. Если присутствует управляющийтокен TRUE, токенданных с входной линии Т пересылается на выходную линию. В результате эти дватокена на входных линиях уничтожаются, но при наличии токена данных на линии F он сохраняется. Еслиприсутствует управляющий токен FALSE,то токен данных на входной линии F пересылается на выходную линию. В результате этого два токенана входных линиях уничтожаются, но токен данных на линии Т, если онприсутствовал,  сохраняется.

ВСГТУ 622-1

Изм.

Лист

еще рефераты
Еще работы по компьютерам и переферийным устройствам