Схемные реализации ФАЛ Напоминание: 1) ИСА (информационная структура алгоритма,) суть граф подстановок композицию функции из базовых функций; 2) ПРФ (примитивно-рекурсивная функция) имеет бесконечный граф подстановок, построенный из повторяющихся фрагментов; 3) процессорная реализация – функции ИСА реализуются либо на единственном универсальном процессоре 1П (однопроцессорное разложение), либо на п процессорах (специализированных или универсальных) – пП-разложение (универсальное), nПс-разложение (специализированное); 4) процессорная реализация имеет т хранящих регистров, где временно хранятся значения рекурсивной функции; 5) количество т регистров может быть минимизировано по теореме А.П. Ершова.
Пара чисел «а» и «b» представляются двоичными кодами. Двоичные коды имеют п разрядов и упорядочены слева направо. , .
Примитивно-рекурсивная функция сумматора на наборе из элементарных функций {, &, }.!Заметим!, что набор не является полным (см. таблицу Поста), в данном случае требование полноты не выдвигается.
Сумматор определяется следующими функциями:
Все операции задаются соответствующими таблицами Si, Ci и Pi.
Таблицы операций поразрядной суммы переноса и сложения задаются исходя из понимания (или необходимости) получения нужных функций. (Fc– функция суммы, Fp– переноса).
Пример построения таблицы и функции Fpпереноса Pi.
Pi-1
ai
bi
Pi
0
0
0
0
0
1
0
0
1
0
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
СДНФ Pi=
Примитивно-рекурсивная функция сумматора ().
Обозначим . , где параметр рекурсии i= 0, 1, 2, …, п – количество разрядов сумматора
a) ;
б) ;
в) .
Комбинационный сумматор.
ИС i-го разряда в виде ЯПФ.
Комбинационная схема сумматора (1-разрядного)
Комбинационная схема n-разрядного сумматора вычисляет сумму в каждом разряде мгновенно «со скоростью света», если одновременно поданы все входные значения <a, b>.
Затраты на оборудование комбинационных схем весьма велики. Для комбинационного п-разрядного сумматора с набором элементарных функций {, &, } число функциональных элементов – 5п, число соединительных проводов – 14п. Но, выполняется суммирование п-разрядных чисел мгновенно, с точностью до физического запаздывания в элементах схемы.
Микропроцессорная реализация сумматора
на трех специальных процессорах.
В данном случае в роли процессоров выступают функциональные элементы П, П, П&, работающие на общее поле памяти.
3П-разложение ИС сумматора представлено на рисунке
К концу 3-го такта регистр r0 хранит значение Ci, полученное во втором такте, r3 хранит значение Pi, r1 и r2 свободны и могут быть использованы для приема ai+1, bi+1 при вычислении следующих Pi+1 и Ci+1.
Таким образом строится микропроцессор из 3-х функциональных элементов и 4-х регистров, работающий за 4 такта. Заметим, что по теореме Ершова min число регистров для реализации алгоритма – три, а r0 (четвертый регистр – внешний) используется для выдачи суммы Ciво вне.
Лекция Реализации posix threads api Стандарт posix допускает различные подходы к реализации многопоточности в рамках одного процесса. Возможны три основных подхода
Напоминание общих фактов Определение. Пара, где Х – множество, неотрицательная функция, определённая называется метрическим пространством, если: а причём
, 
.
. 
, где параметр рекурсии i = 0, 1, 2, …, п – количество разрядов сумматора
;
;
.
Схема микропроцессора пред-
