Проблемы синхронизации процессов в асинхронном параллельном цифровом автомате

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

15 пФ, что существенно ниже типовых значений 50−100 пФ для тестеров.
Не слишком широкое применение стандарта 1149.4 при тестировании АЦИМ в процессе их производства объясняется рядом причин, одной из которых является значительная стоимость площади кремниевых пластин, необходимой для реализации большого количества модулей АВМ. Кроме того, в последнее время весьма популярен подход к тестированию кремниевых пластин с пониженным числом точек доступа как средство снижения стоимо -сти теста микросхем, содержащих структуры внутреннего или граничного сканирования, встроенные средства самотестирования и т. п. Предлагаемый в данной работе метод обеспечения структурной тестопригодности АЦИМ с резко сокращенным набором модулей АВМ может быть очень удобен для быстрой генерации тестов аналоговых кластеров внутри самого функционального ядра, для тестирования низкочастотных внутренних выводов ядра АЦИМ с пониженным числом точек доступа [10], а также для параметрического тестирования внешних выводов АЦИМ. Такой подход может оказаться приемлем в процессе разработки микросхем и на ранних стадиях отладочного тестирования внутренней логики и встроенных модулей памяти, когда еще можно учесть и принять любые изменения их структуры. Количество внутренних выводов ядра АЦИМ, подключенных к мультиплексорам на ранних стадиях тестирования, затем может быть существенно уменьшено в финальной версии структуры АЦИМ.
Стоимость современных АЦИМ возрастает экспоненциально, поэтому жизненно важным экономическим требованием является подход к их разработ-
УДК 681. 324. 01 '-
ПРОБЛЕМЫ СИНХРОНИЗАЦИИ ПРОЦЕССОВ В АСИНХРОННОМ ПАРАЛЛЕЛЬНОМ ЦИФРОВОМ АВТОМАТЕ
НЕМЧЕНКО А.В. ___________________________
Анализируется математическая модель асинхронного параллельного цифрового автомата, реализующего параллельный алгоритм. Рассматриваются вопросы взаимодействия асинхронных процессов и проблемы, возникающие при этом.
Введение
Производители микропрограммных устройств — микроконтроллеров, микропроцессоров, DSP и т. д. — применяют различные методы и технологии для повышения производительности своей продукции. В основном это стандартные средства — конвейеризация, улучшение системы прерываний, перенос части логических функций и программ на аппаратный уровень (например, автоматизация передачи данных по протоколу RS-232). Одной из таких последних технологий от фирмы Intel явля-
РИ, 2005, № 3
ке с применением повторно используемых структурных блоков, заранее снабженных средствами тестирования этих блоков. Описанная в данной работе тестовая структура применима также при проектировании систем на кристалле SOC [11], совместимых со стандартом IEEE 1500, как составная часть повторно используемой иерархической тестовой структуры граничного сканирования.
Литература: 1. Gorodetsky A. Strategy of Boundary-Scan On-Board Activity", Technologies // Israel' Magazine of High Technology, vol. 223, August 2001, Р. 154−158 (Hebrew). 2. FilliterK. Virtual Analog Probes Using IEEE
1149.1 (A Concept IC) // 3rd IEEE International Board Test Workshop, 2004. 3. Городецкий AРустинов В. Разделяй и властвуй — принцип граничного сканирования // ChipNews, Москва, 2001. № 6. С. 14−19. 4. IEEE Standard for a Mixed-Signal Test Bus // IEEE Std 1149. 4−1999. 5. The Boundary-Scan Handbook. 3rd Edition, by K.P. Parker, Kluwer Academic Pub, 2003. 6. Analog and Mixed-Signal Boundary-Scan. Ed. by A. Osseiran, Kluwer Academic Pub., 1999. 7. Sunter S.K. andNadeau-Dostie B. Complete, Contactless I/O Testing — Reaching the Boundary in Minimizing Digital IC Testing Cost // Proc. of ITC.P. 446−455. 2002. 8. SCANSTA400 IEEE 1149.4 Analog Test Access Device // National Semiconductor Advanced Information, August 2000. 9. DuzevikI. Preliminary Results of Passive Component Measurement Methods Using an IEEE 1149.4 Compliant Device // 1st IEEE International Board Test Workshop, 2002. 10. Ben Bennetts. Guidelines for Chip Design For Test Based on Boundary-Scan", Asset InterTech Inc. web site, 2003. 11. Sehgal A. etal. IEEE P1500-Compliant Test Wrapper Design for Hierarchical Cores // Proc. of ITC. 2004. P. 1203−1212.
Поступила в редколлегию 22. 08. 2005
Рецензент: д-р техн. наук, проф. Хаханов В. И.
Ами Городецкий, Testability (Израиль). Тел. +972 544 621 834, amigo@TestabilityScan. com
ется реализация в архитектуре процессора реального параллелизма — выпуск процессоров с двумя ядрами. Такие чипы, помимо двух ядер, получат поддержку технологии многопоточности HyperThreading (HT). Технология Н Т позволяет операционной системе рассматривать один физический процессор в качестве двух логических. Таким образом, двуядерные Pentium Extreme Edition позволят обрабатывать одновременно четыре потока инструкций [http: //hard. compulenta. ru/ 170 439].
Все это говорит о том, что в плане повышения производительности средств вычислительной техники вопросы параллелизма являются весьма актуальными и перспективными. Отметим также, что в работе [1] проведен глубокий анализ проблемы параллелизма и показана ее актуальность.
В работе [2] автор описал математическую модель параллельного цифрового автомата (ПЦА). Была затронута тема асинхронного параллелизма-работа параллельных устройств с разной синхронизацией и сбросом. Был показан способ их синтеза, который позволяет с небольшими аппаратными затратами создавать устройства, работающие по сложным алгоритмам.
95
В процессе моделирования работы таких устройств выявились серьезные проблемы при взаимодействии асинхронных алгоритмов — неустойчивость работы при смене состояний двух процессов. В данной статье ставится задача определить природу этой проблемы, формализовать ее и показать пути уменьшения рисков сбоя в работе параллельных автоматов. Таким образом, целью данного исследования является анализ и решение проблемы синхронизации процессов в асинхронном параллельном цифровом автомате.
Асинхронный параллельный цифровой автомат
Асинхронный параллельный цифровой автомат (АПЦА) может быть представлен следующей иерархической моделью (рис. 1).
| Интерфейс АПЦА |
X
_______________І___________________
| Взаимодействие процессов |
X X
т т
I Процесс I I Процесс I
JT дЗч
| Поток | | Поток | | Поток | | Поток |
Рис. 1. Иерархическая модель АПЦА
На нижнем уровне находится поток, — аналог последовательного ЦА. Он может быть описан следующей математической моделью:
Thj =
A1 = {a0,a1,…, ak>-, Xі = {xj, x2,…, xj}, Y1 = {Уі, У2'… 'Ут}'
a0 є A1,
a1 (TfJ) = 5(Aj (Ti[ _1), X1(Ti- _j))5 Y1 (Tj[) = X (Ajj (Tj[), X1(Tji)).
Эта модель была подробно рассмотрена в [2].
(1)
В системе (1) используется модель автоматного времени (АВ). В [3] показано, что для рассмотрения работы ЦА (в данном контексте — потока) достаточно знать смену времен и игнорировать промежутки времени смены состояния. АВ представляет из себя дискретное множество Ti = {0, 1, …}.
Модель автоматного времени представлена на рис. 2.
s е
Л
? «Я н! Г О
о
о «Ч н с,
X
ЛК Л».
ti
К, т.
X, А X
Реальное время:
Автоматное
время: '-
Рис. 2. Модель автоматного времени
Из рис. 2 видно, что автомат пребывает в одном состоянии в течение ti с. За это время происходит два события — смена состояния длительностью At x и устойчивая работа в новом состоянии aj длительностью Ata.
Множество потоков объединяется в один процесс: Aj = {A1,A2,…, An},
X = {X1 uX2 u… u Xn, CLK, Reset},
Y = {Y1 u Y2 u… u Yn},
Prj =
A0 є Aj-
Thj = {Th1,ThJ2,…, ThJn},
Tj = Ftj (t, T|*, CLK, Reset).
(2)
Для всех потоков данного процесса определяется одна и та же функция автоматного времени (ФАВ) T1. Как видно из (2), ФАВ зависит от реального времени t, текущего АВ Tkj, сигнала синхронизации CLK и сигнала сброса Reset (эти два сигнала являются частью множества всех входных сигналов X данного процесса).
ФАВ определяется исходя из особенностей функционирования моделируемого объекта. Например, для реальных цифровых схем, период работы которых строго периодичен, ФАВ может быть описана следующим образом:
Ftj =
Tk
Tk
CLK
ATj ^Tk+1'
Reset
-& gt-Tj
^ V
t (Tk) = A t
a
0 & lt- t (Tk ^ TjJ+1) & lt-Atx
Atx, Ata & gt- 0.
(3)
Первая строка говорит о том, что при поступлении сигнала CLK автоматное время инкрементируется. Вторая строка говорит, что сигнал Reset сбрасывает автомат в начальный момент АВ. Третья строка определяет время пребывания процесса в устойчивом состоянии. Четвертая показывает, что время смены состояния конечно и меньше либо равно некоторой константе. Пятая строка определяет тот факт, что эти два времени положительны.
Для случая модели, где не нужно учитывать время смены состояния, четвертая строка выглядит как
•& lt-Tk ^ Tk+1)=0 • (4& gt-
При нестрогой синхронизации третья строка (3) выглядит как
t (Tk) & gt- 0. (5)
Графически процесс может быть представлен так, как это изображено на рис. 3.
96
РИ, 2005, № 3
Рис. 3. Функционирование процесса
Из рис. 3 видно, что на вход процесса подается множество входных воздействий Xj, с выхода снимается Yj. Смена автоматного времени осуществляется сигналами CLK и Reset. Смена состояния происходит в течение времени д tx. Время пребывания автомата в заданном состоянии также ненулевое (д ta& gt-0).
Один процесс работает «синхронно» — в одном автоматном времени. Множество процессов работают «асинхронно» — у них разное автоматное время. Следовательно, процесс реализует синхронный параллелизм, множество процессов — асинхронный параллелизм. Пример последнего приведен на рис. 4.
является переход в процессе Pr2 3 из состояния а4 В состояние а5 в момент автоматного времени T 22.
На рис. 5 показан процесс смены состояний двух процессов в абсолютном времени, приводящий к возникновению проблемы взаимонеустойчивости.
Рис. 5. Проблема взаимонеустойчивости
Из рис. 5 видно, что есть моменты, когда оба процесса одновременно пребывают в неустойчивых состояниях. Рис. 6 поясняет возникновение неустойчивого состояния.
а, X

& gt-
Из рис. 4 видно, что один поток влияет на работу другого. В частности, следствием состояния а2 в процессе Pr* 1 в момент автоматного времени Т21
*-
t
Рис. 6. Неустойчивое состояние
Весь период неустойчивого состояния можно разбить на три части:
1) At^mem: от внешних входов системы переменная передается к элементам памяти, проходя через каскады комбинационной схемы-
2) Atmem: элементы памяти меняют свое состояние-
3) Atmem^: новое состояние от элементов памяти достигает внешних выходов системы, проходя через каскады комбинационной схемы.
Очевидно, что если первый процесс находится в Atmem^, а второй — в Atmem, то будет передана некорректная информация.
Упомянутая проблема взаимонеустойчивости накладывает серьезные ограничения на применение асинхронного параллелизма. Впрочем, как будет показано далее, для случая строго периодически синхронизируемых процессов есть возможность
РИ, 2005, № 3
97
предсказать взаимонеустойчивые моменты времени. Уровень взаимодействия процессов призван решать эту проблему.
Наконец, на уровне интерфейса АЦПА рассматривается множество процессов. Этот уровень может быть описан следующей системой:
S
Pr = {Pr1,Pr2,…, Prn},
X = {x1,x2,…, xm},
1 «2
v & lt-¦ 1 2 k.
Y = {y, y ,…, y }.
Графическая иллюстрация системы уравнений приведена на рис. 7.
(6)
(6)
Рис. 7. Уровень интерфейса АПЦА
Проблема взаимонеустойчивости
Как было показано ранее, при взаимодействии взаимонесинхронизированных процессов приходится оперировать реальным временем, а не АВ. При этом из-за конечности скорости распространения сигналов в схеме могут возникать взаимонеустойчивые состояния.
Для системы (3) промежутки времени неустойчивой работы можно описать следующим неравенством (будем считать, что смена состояния происходит в первый момент времени):
(AtX + AtX) n + AtX & gt- t & gt- (AtX + AtX) n, n = 0,1,2,…
(7)
Здесь (д tx1+ A ta1) — длительность одного процесса, или период тактирования. Если его заменить на t1, то (7) можно записать более компактно:
tjn + AtX & gt- t & gt- tjn, n = 0,1,2,… (8)
Если взять два процесса, найти их периоды неустойчивой работы в форме (8) и пересечь, то мы получим период взаимонеустойчивой работы двух процессов:
Jtjn + AtX ^ t & gt- tjn, n = 0,1,2,… -
jtjm + Apx & gt- t & gt- tjm, m = 0,1,2,… (9)
Таким образом, для двух строго синхронизируемых процессов можно найти промежутки времени, когда оба процесса взаимонеустойчивы.
Система (9) дает решение в виде множеств, но она не позволяет увидеть решение в графическом виде. Для этого надо представить протекание процесса в волновом виде:
sin (ra *t + ф) & gt- A. (10)
Формула (10) дает решение, эквивалентное (7), если считать, что A задает соотношение времени неустойчивого и устойчивого протекания процесса, v определяет период синхронизации, а Ф определяет, когда (внутри одного такта синхронизации) происходит смена состояния. На рис. 8 представлена графическая интерпретация процесса в волновом виде.
Если просуммировать выражение (10) для двух процессов, то получим соотношение, описывающее периоды взаимонеустойчивой работы процессов:
sin^t + Ф1)+sin (ra2t + Ф2) ^ A1 + A2. (11)
Если частоты двух колебаний приблизительно равны, то в итоге возникают биения:
sin (® модt + Фмод) cos (®огt + Фог) — A сум. (12)
Отметим, что в формуле (12) произведены замены переменных.
В графическом виде уравнение (12) представлено на рис. 9.
Рис. 9. Сложение двух колебаний
98
РИ, 2005, № 3
Анализ показывает, что длительное время процессы взаимоустойчивы. Однако наступает промежуток времени, когда взаимонеустойчивость проявляется строго периодично — с частотой юмод.
Промежутки времени неустойчивой работы вначале короткие, потом становятся длиннее. Максимальная ширина не превышает полупериод моду. 1
лирующей синусоиды: -. Затем про-
юмод
межутки времени уменьшаются. Динамика этого процесса изображена на рис. 10. Чем ближе друг к другу частоты обоих процессов, тем четче вцдны биения.
Рис. 10. Характер биений
Очевидно, что результаты решения системы (9) можно использовать на практике. Здесь речь идет о некотором блоке предсказания взаимонеустойчивых состояний. В том случае, если такие состояния наступают, имеет смысл пропускать такты работы устройства:
Tk CLK & gt- Tk. (13)
Представляется целесообразным и возможным реализовать на практике некоторое устройство, кото -рое будет приостанавливать функционирование взаимонеустойчивых процессов АП ЦА в моменты их неустойчивой работы. Другими словами — риски сбоя в работе автомата можно уменьшить.
Напомним, что предсказать взаимонеустойчивые моменты времени можно только для строго синхронизируемых процессов. В противном случае прогнозирование невозможно или требует больших затрат для его осуществления.
УДК 519. 713 '-
МЕТОДЫ ОЦЕНКИ КАЧЕСТВА IP-ТЕЛЕФОНИИ
ГЕМА В.С., ЧИКИНА В.А. ___________________
Описывается классификация методов определения качества голосового трафика поверх IP-сети, а также сравнительный анализ субъективных и автоматических методов оценки качества предоставляемых услуг.
1. Введение
IP-телефония является наиболее перспективным средством связи. Десятки компаний по всему миру предлагают коммерческие решения для IP-телефонии. Однако на сегодняшний день качество обслуживания клиента, как комплексный параметр, является одним из наиболее актуальных моментов при предоставлении любых услуг связи, так как при этом сталкиваются интересы поставщиков и
Выводы
Проведенный анализ взаимодействия параллельных процессов в асинхронных цифровых автоматах показывает, что при достаточно близких тактовых частотах в двух параллельных асинхронных процессах возникают моменты взаимонеустойчивого функционирования. Данный процесс имеет периодичный характер и может быть предсказан на основании предложенной модели.
По мнению автора, предложенный подход к анализу взаимодействия параллельных процессов является в определенной степени универсальным. Его научная новизна заключается в использовании математического аппарата, применяемого для описания волновых процессов.
Предложенный метод анализа взаимодействия асинхронных параллельных процессов может быть применен в различных областях, где имеет место распараллеливание процессов-задачи моделирования социальных процессов, транспортные задачи, проблемы оптимального распараллеливания задач в сложных системах, для согласования сложных распределенных транзакций и т. п.
Литература: 1. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с. 2. Nemchenko O, Krivoulya G. Use of parallelism in finite state machines. Mathematical level. EWDTW'04. Yalta, Crimea, Ukraine, September 23−26, 2004. P. 210 213. 3. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.
Поступила в редколлегию 20. 06. 2005
Рецензент: д-р техн. наук, проф. Кривуля Г. Ф.
Немченко Александр Владимирович, аспирант ХНУРЭ. Научные интересы: оптимизация организации вычислительных процессов в компьютерных системах, параллелизм в системах, компьютерное моделирование. Адрес: Украина, 61 166, Харьков, пр. Ленина, 14, тел.: 70−21−326, e-mail: alexandre_n@mail. ru.
потребителей услуг. Это вызвано, прежде всего, объективными причинами — интересы поставщиков и потребителей всегда в известной степени противоречат друг другу. И задача оператора сети связи найти оптимальное решение для удовлетворения как собственных интересов, так и интересов потребителей услуг. Таким образом, методы оценки качества передачи голоса заслуживают отдельного внимания в связи со стремительным развитием IP-телефонии и достижением ею уровня развития телефонов общего пользования (ТфОП).
В литературе основные аспекты, структура и принципы работы IP-телефонии описаны довольно детально. Исследованы основы технологии передачи речи по сетям пакетной коммутации, работающим по протоколу IP (Internet Protocol) [1]. Рассмотрены архитектуры системы IP-телефонии на базе Рекомендаций ITU-T (International Telecommunication Union) H. 323 и концепции TIPHON, разработанной ETSI (European
РИ, 2005, № 3
99

ПоказатьСвернуть
Заполнить форму текущей работой