Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Операция поиска минимума.
|
|
В качестве кандидата на минимум при анализе текущего среза данных рассматриваются те ячейки памяти, у которых бит равен 0. При поиске минимума также возникают ситуации особые 1-го и 2-го рода:
1. особая ситуация при единичном срезе данных;
2. особая ситуация, при которой нулевые биты в срезе данных соответствуют единичным битам в предыдущей поисковой функции.
| 1 | Fmin | |||||||
| F0 | F1 | F2 | F3 | F4 | ||||
| S 0 | 1 |
При организации поиска по 3-му срезу данных возникает особая ситуация 1-го рода, поэтому F3 не вычисляется, а берется от предыдущего значения. Рассмотрим синтез ячейки накопителя для операции поиска минимума.
| M1j | Fminij-1 | Si | Qij | Fminij | |
| т. к. М1i = 0 | |||||
| Т. к. Fi-1j = 0 | |||||
Рис. 21.
Операции ассоциативного поиска всех больших (F> ), F< , F≥ , F≤ .
Особенность реализации данных операций связана с вычислением по каждому срезу данных двух поисковых функций.
| M1i |
| Vi, j |
| Zi, j |
| Яij Qij |
| Ai |
| M1j |
| Zi-1, j |
| Vi-1, j |
(A > Q первый раз)
(A ≤ Q во всех предыдущих разрядах)
В данные функции необходимо ввести бит маски. Окончательное решение об установлении отношений F> , F< , F≥ , F≤ выносится на основе анализа поисковой функции для последнего среза данных.
| Vm | Zm | Соотношение |
| Q < A | ||
| Q = A | ||
| Q > A | ||
Операции поиска ближайшего большего и ближайшего меньшего.
Особенность данных операций определяется тем, что они реализуются в 2 этапа.
Fбб = min (>)
I этап – находятся все большие
II этап – среди них ищется минимум
Fбм = max (<)
I этап – ищутся минимумы
II этап – ищется среди них максимум
После выполнения первого этапа найденное значение поисковой функции записывается в маску Mz. Второй этап будет осуществляться только для тех ячеек накопителя, у которых M2i = 1.
Лекция №9