Многопроцессорные вычислительные системы
Общее количество кодовых комбинаций может быть меньше или равно числу всевозможных комбинаций из заданного количества символов. Наиболее известные из самоконтролирующихся и самокорректирующихся кодов – коды Хемминга.Основы вычислительных систем
 |
Информационная зависимость фрагментов программ (ФП) играет определяющую роль при построении параллельных программ. Однако при решении задачи распараллеливания последовательных алгоритмов следует учитывать и логическую подчиненность ФП, которая может существенно препятствовать распараллеливанию наиболее сильно связанных на элементарном уровне ФП. В связи с этим в моделях программ, ориентированных на микроуровень ФП, требуется в значительной степени отражать режим управления вычислениями с учетом логической подчиненности ФП в исходных последовательных схемах и программах. В этом плане достаточно удобен и пригоден для практических целей аппарат сетей Петри, на базе которого построен целый ряд моделей параллельных вычислений. Графически сеть Петри изображается как ориентированный бихроматический граф (рис. 5.6). восстановление волос цены
Иногда функцию инцидентности F как компоненту сети Петри представляют в виде двух функций: PRE: P´T ®í0,1ý, POST : T´P→ {0,1}.
Из вершины pÎP в вершину tÎT дуга ведет тогда и только тогда, когда PRE(p, t) = 1, а из вершины tÎT в вершину pÎP тогда и только тогда, когда POST (t, p) = 1. Разметка изображается точками в местах.
Разметка сети позволяет описывать ее состояние. Функционирование сети Петри происходит посредством перехода от одной разметки к другой. Изменение разметок происходит вследствие срабатывания переходов. Переход t может сработать, если для него выполнено условие "p (M(p) – PRE (p, t) ≥ 0),
где M – текущая разметка. В нашем примере такому условию удовлетворяют переходы t1 и t2. Срабатывание перехода t приводит к изменению разметки: входные места перехода теряют по одной метке, а выходные – получают по одной метке.
Разметку M сети называют достижимой из M0, если существует последовательность срабатываний переходов, в результате которой разметка сети из M0 переходит в M. Рассмотрим формальную модель программ, в основу которой положено специальное расширение сетей Петри – ПМ-сети.
Обобщенная сеть Петри – это набор (P, T, F, H, M0), где P – множество мест; T – множество переходов; F: P´T®N∪{0} и H: T´P®N∪{0} – функция инцидентности; M0: P®N∪{0} – начальная разметка; N – множество натуральных чисел.
Определим для сетей два типа меток: плюс-метки и минус-метки, соответственно расширим область значений функции разметки: M: P®{ …, -1, 0, 1, …}. Обозначим P+ = {p| M(p)>0}, P- = {p| M (p) < 0}. Введем функционал (предикатный функционал) C: H∪F®{+, -}, т. е. каждая дуга сети помечается либо плюсом, либо минусом.
Изменим в соответствии с введенными дополнениями и правила функционирования сетей. Будем считать, что одновременно в месте не могут находиться плюс- и минус-метки. В связи с этим определим операцию аннигиляции меток, т. е. операцию одновременного уничтожения равного количества плюс- и минус-меток для одного и того же места.
Будем
использовать следующие обозначения: *t = {p| F (p, t)>0}; t* =
= {p|
H (t, p)>0}; *t+ (*t-) – множество таких мест, что существуют
дуги из этих мест в переход и эти дуги помечены плюсом (минусом); t+*(t-*)
– множество таких мест, что существуют дуги из перехода t в эти места и эти дуги
помечены плюсом (минусом). Отметим, что *t+∩*t- =
Ø для любого t, т. е. если из места в переход существуют кратные дуги,
то они должны быть помечены одним и тем же символом. Иначе из-за операции аннигиляции
невозможно включение перехода t и он будет заведомо недостижим от любой начальной
разметки сети.
Переход t может сработать, если для него выполнены условия:
а) для "pÎ*t+ имеет место M(p)≥F(p, t),
б) для "pÎ*t- имеет место M(p)<0 и |M(p)|≥F(p, t).
Срабатывание перехода t приводит к изменению разметки M на M/ по правилам:
1) если pÎt-*, то M/(p) = M(p) – H(t, p);
2) если pÎt+*, то M/(p) = M(p) + H(t, p);
3) если pÎ*t-, то M/(p) = M (p) + F(p, t);
4) если pÎ*t+, то M/(p) = M (p) – F(p, t);
5) если pÎ *t∪t*, то M/(p) = M(p).
Дело в том, что разработанные программы и подготовленные данные для отдельного компьютера и предназначенные для локального использования, практически не содержали средств защиты Проблема обеспечения достоверности функционирования ВС имеет много общего с проблемой достоверности передачи дискретной информации по каналам связи (КС).