Моделирование конвейерных и волновых вычислений

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

1

http://naukovedenie.ru 56TVN114

УДК
004.9

Кудряшова Екатерина Сергеевна

ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет»

Россия, Комсомольск-на-Амуре1

Аспирант, ассистент

E-Mail: ekatt@inbox.ru

Михайлова Наталья Николаевна

ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет»

Россия, Комсомольск-на-Амуре

Старший преподаватель

E-Mail: mnataly4217@yandex.ru

Хусаинов Ахмет Аксанович

ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет»

Россия, Комсомольск-на-Амуре

Доктор физико-математических наук, профессор

E-Mail: husainov51@yandex.ru

Моделирование конвейерных и волновых вычислений

Аннотация: Предложена компьютерная модель многопроцессорного асинхронного 

вычислительного конвейера с буферной памятью. Она допускает программную реализацию с 
помощью многопоточного приложения на языке С++ под управлением операционных систем 
Windows XP, Windows 7. Эксперименты с компьютерной моделью были проведены на 
различных процессорах, включая Intel(R) Core(TM) i3-2310M CPU. Роль функциональных 
устройств играют потоки. Буферная память программно реализована с помощью объектов 
класса канал, имеющего операции записи и чтения, работающие по алгоритму Дейкстры для 
решения задачи о производителе и потребителе. Экспериментально установлено, что эта 
модель может быть применена для исследования производительности и историй параллельного 
процесса, состоящего из вычислительных операций и операций передачи данных между 
функциональными устройствами асинхронного конвейера. Приведены графики зависимости 
ускорения от объема входных данных, полученные с помощью эксперимента. Эти графики 
подтверждают формулу для расчета ускорения асинхронного конвейера. На основании
исследования ускорения с помощью этой компьютерной модели сделаны выводы о том, что 
ускорение для асинхронного линейного конвейера не зависит от объема буферной памяти.
Рассмотрено использование этой модели для изучения явления пузырька в конвейере. Эта 
модель расширена также для имитации работы волновой системы. Для волновой системы 
высказана и экспериментально проверена гипотеза о линейной зависимости времени обработки 
данных от их объема.

Ключевые слова: Вычислительный конвейер; асинхронный конвейер; буферная 

память; сеть Петри; расчет производительности; каналы ОС Unix; многопоточное приложение; 
семафор; ускорение параллельного выполнения; задача о производителе и потребителе; трасса; 
волновая система; объектно-ориентированное программирование.

Идентификационный номер статьи в журнале 56TVN114

1 681013 Россия, г. Комсомольск–на–Амуре, пр. Ленина, д. 27

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

2

http://naukovedenie.ru 56TVN114

Ekaterina Kudryashova

Komsomolsk-on-Amur State Technical University

Russia, Komsomolsk-on-Amur

E-Mail: ekatt@inbox.ru

Natalya Mikhailova

Komsomolsk-on-Amur State Technical University

Russia, Komsomolsk-on-Amur

E-Mail: mnataly4217@yandex.ru

Ahmet Husainov

Komsomolsk-on-Amur State Technical University

Russia, Komsomolsk-on-Amur
E-Mail: husainov51@yandex.ru

Modeling of pipeline and wave computations

Abstract: A computer model of asynchronous multiprocessor computing pipeline with a buffer 

storage is proposed. The model allows the software implementation using the multi-threaded 
application written in C++ running under operating systems Windows XP, Windows 7. The
experiments with the computer model were performed on a variety of processors, including the Intel(R) 
Core(TM) i3-2310M CPU. Threads act as functional devices. The buffer storage is implemented using 
class channel objects. It has read and write operations, working on the Dijkstra algorithm for solving 
the producer-consumer problem. Experimentally established that this model can be used to study the 
performance and the histories of the parallel process, which consists of computing operations and data 
transfer operations between functional units of asynchronous pipeline. The plots of speedup depending 
on the number of input data, obtained by experiment, are shown. These plots confirm the formula for 
calculating the speedup for the asynchronous pipeline. Conclusions are obtained that a speedup for the 
asynchronous pipeline is independent on the volume of its buffer storage. This model is considered for 
studying the bubble effect in the pipeline. The model is also extended to simulate a wave system. For 
the wave system, it is suggested and experimentally tested a conjecture of a linear dependence of the 
data on their volume.

Keywords: Computational pipeline; asynchronous pipeline; buffer storage; Petri net; 

performance computation; OS Unix channel; multithreaded application; semaphore; parallel 
processing speedup; producer-consumer problem; trace; wave system; object-oriented programming.

Identification number of article 56TVN114

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

3

http://naukovedenie.ru 56TVN114

Введение

Вычислительная волновая система состоит из функциональных устройств и каналов для 

передачи данных между этими устройствами. Мы моделируем каналы с помощью каналов ОС 
Unix [1], а функциональные устройства – с помощью потоков (нитей). Вычислительная 
волновая система должна удовлетворять следующим условиям:

1.
Каждый канал имеет единственное функциональное устройство, считывающее
данные из этого канала или единственное устройство, записывающее данные в 
этот канал (или и то, и другое).

2.
Для каждого функционального устройства существует, по крайней мере, один 
канал, в который это устройство записывает, и, по крайней мере, один канал, из 
которого оно считывает.

3.
Всякая цепь, состоящая из соединений каналов со считывающими из них 
функциональными устройствами и соединений этих устройств с каналами, в 
которые они записывают, не имеет циклов.

Таким образом, волновая система является обобщением линейного конвейера в смысле 

[2] и частным случаем нелинейного конвейера [2]. Волновая система может быть реализована 
как сеть транспьютеров и составлять вычислительную систему с высокой интенсивностью 
вычислений и большими объемами входных и выходных данных. Она во многом похожа на 
систолическую матрицу. Но в волновой системе отсутствует глобальная система 
синхронизации. Волновая система является асинхронной.

Если канал не имеет устройства, записывающего в него данные, то он называется 

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

производительности, в каждый из ее входных каналов записывается n элементов данных.

Особенно широко применяются асинхронные линейные конвейеры, начиная с уровня 

обработки запросов в параллельных системах управления базами данных [3] и кончая уровнем 
вентильной реализации [4]. По этой причине мы сначала предлагаем компьютерную модель для 
исследования линейного конвейера. Мы решаем проблему, связанную с тем, что всякий 
конвейер является многопроцессорной системой. Мы предлагаем модель, реализуемую на 
компьютере, имеющем один процессор. Эта компьютерная модель может быть применена для 
оценки ускорения. Она может быть применена также для описания истории действий, 
происходящих в вычислительном конвейере.

Каждое функциональное устройство выполняет цикл, включающий чтение данных из 

входного канала, выполнение операции и запись результата операции в выходной канал.
Функциональные устройства имеют различную скорость выполнения. Каналы могут иметь 
различные времена чтения и записи. Один канал не может работать одновременно с двумя 
функциональными устройствами. Если каждый канал состоит из одного регистра, а скорости 
выполнения операций одинаковы, мы получаем синхронный линейный конвейер [2].

Руководствуясь простыми соображениями можно получить формулу для нахождения 

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

экспериментально.

Похожая формула рассматривается в [5], где время выполнения операций может быть 

различным. Но в [5] предполагается, что скорость обмена данными между каналами и 
функциональными устройствами одинакова, а чтение из канала и запись в этот канал может 

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

4

http://naukovedenie.ru 56TVN114

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

Формула для нахождения ускорения

Рассмотрим конвейер, состоящий из 𝑝 функциональных устройств и 𝑝 + 1 каналов

𝑐0, … , 𝑐𝑝. Пусть 𝑢𝑖 - последовательность действий, выполняемых за 1 шаг, 0 ≤ 𝑖 ≤ 𝑝 − 1. Она 
состоит из чтения из канала 𝑐𝑖, вычислительной операции 𝑎𝑖 и записи в канал 𝑐𝑖+1. Время 
выполнения 𝑢𝑖 равно 𝑟(𝑐𝑖) + 𝜏(𝑎𝑖) + 𝑤(𝑐𝑖+1), где 𝑟(𝑐𝑖) обозначает время чтения из канала 𝑐𝑖, 
𝑤(𝑐𝑖) - время записи в канал 𝑐𝑖, 𝜏(𝑎𝑖) - время выполнения операции 𝑎𝑖, 0 ≤ 𝑖 ≤ 𝑝 − 1.

Под ускорением 𝑆𝑝(𝑛) мы будем подразумевать отношение 

𝑇𝑠𝑒𝑞
𝑇𝑝
времени 𝑇𝑠𝑒𝑞

последовательного выполнения вычислительных операций над 𝑛 элементами входных данных 
к времени 𝑇𝑝 параллельного выполнения этих операций с помощью 𝑝 процессоров. Ускорение 

можно определить также как отношение

𝑇1
𝑇𝑝 .

Одной из наших задач будет экспериментальное подтверждение следующей формулы 

для расчета ускорения для асинхронного вычислительного конвейера с буферной памятью:

𝑆𝑝(𝑛) =

𝑛 ∑
𝜏(𝑎𝑖)
𝑝−1
𝑖=1

∑
(𝑟(𝑐𝑖)+𝜏(𝑎𝑖)+𝑤(𝑐𝑖+1))
𝑝−1
𝑖=1
+(𝑛−1)
max

0≤𝑖≤𝑝−1{𝑟(𝑐𝑖)+𝜏(𝑎𝑖)+𝑤(𝑐𝑖+1)} .
(1)

Мы не будем использовать эту формулу для вывода каких-либо утверждений. Ее пока 

можно считать гипотетической.

Математическая модель

Пусть ℕ = {0,1,2 … } - множество неотрицательных целых чисел. Для произвольного 

конечного множества 𝑃 обозначим через ℕ𝑝 множество функций 𝑀: 𝑃 → ℕ. Сетью Петри 
называется четверка (𝑃, 𝑇, 𝑝𝑟𝑒, 𝑝𝑜𝑠𝑡, 𝑀0), состоящая из произвольных конечных множеств 𝑃 =
{𝑝0, … , 𝑝𝑛−1} и 𝑇 = {𝑡0, … , 𝑡𝑚−1}, функций 𝑝𝑟𝑒, 𝑝𝑜𝑠𝑡: 𝑇 → ℕ𝑝 и функции 𝑀0: 𝑃 → ℕ. Элементы 
из 𝑃 называются местами, а из 𝑇 - переходами. Маркировкой называется функция 𝑀: 𝑃 → ℕ. 
Функция 𝑀0 называется начальной маркировкой.

Сеть Петри наглядно изображается с помощью кругов, прямоугольников и стрелок. 

Места изображаются в виде кругов, переходам соответствуют прямоугольники. Для всех 𝑡𝑖 ∈ 𝑇
значения функций 𝑝𝑟𝑒, 𝑝𝑜𝑠𝑡: 𝑇 → ℕ𝑝 сами будут функциями 𝑝𝑟𝑒(𝑡𝑖): 𝑃 → ℕ, 𝑝𝑜𝑠𝑡(𝑡𝑖): 𝑃 → ℕ. 
Если 𝑝𝑟𝑒(𝑡𝑖)(𝑝𝑗) = 𝑘 > 0, то рисуется 𝑘 стрелок с началом в круге 𝑝𝑗 и с концом в 
прямоугольнике 𝑡𝑖. Если 𝑝𝑜𝑠𝑡(𝑡𝑖)(𝑝𝑗) = 𝑘 > 0, то проводится 𝑘 стрелок от перехода 𝑡𝑖 к месту
𝑝𝑗. Кроме того, для указания значений маркировки, рисуются точки в кругах. Если 𝑀(𝑝𝑖) = 𝑘 >
0, то в месте 𝑝𝑖 рисуется 𝑘 фишек.

Состояния сети Петри определены маркировками, которые получаются из начальной с 

помощью последовательности срабатывания переходов. Переход 𝑡𝑖 называется допускающим 
срабатывание, если для текущей маркировки M для всех 𝑝𝑗 ∈ 𝑃 имеют место неравенства 
𝑝𝑟𝑒(𝑡𝑖)(𝑝𝑗) ≥ 𝑀(𝑝𝑗). В этом случае говорят, что маркировка M’ получена в результате 
срабатывания перехода, если для всех 𝑝𝑗 ∈ 𝑃
верно 𝑀′(𝑝𝑗) = 𝑀(𝑝𝑗) − 𝑝𝑟𝑒(𝑡𝑖)(𝑝𝑗) +

𝑝𝑜𝑠𝑡(𝑡𝑖)(𝑝𝑗).

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

5

http://naukovedenie.ru 56TVN114

Вычислительный конвейер, во входной канал которого записано 𝑛 входных элементов, 

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

Рис. 1. Конвейер из четырех функциональных устройств

Для каждого функционального устройства 𝑢𝑖, 0 ≤ 𝑖 ≤ 𝑝 − 1, задано время выполнения. 

Функциональное устройство выполняет последовательно чтение из канала 𝑐𝑖, вычисление 
операции 𝑎𝑖 и запись в канал 𝑐𝑖+1, 0 ≤ 𝑖 ≤ 𝑝 − 1. Время выполнения обозначим через 𝜏(𝑢𝑖). 
Имеет место равенство 𝜏(𝑢𝑖) = 𝑟(𝑐𝑖) + 𝜏(𝑎𝑖) + 𝑤(𝑐𝑖+1). Для сетей Петри вводится отношение 
независимости, при котором два перехода независимы, если они не имеют общих входных и 
выходных мест. В сети Петри на рисунке 1 переходы 𝑢0 и 𝑢1 зависимы, поскольку во время 
записи устройство 𝑢0 должно захватить канал, из которого читает устройство 𝑢1. Для того,
чтобы учесть это правило, мы измельчаем переходы сети Петри на переходы, время работы 
которых равно 1. Для того чтобы переходы, полученные после измельчения перехода 𝑢𝑖, 
выполнялись как последовательная подпрограмма, мы добавим сверху место с фишкой, 
соединенное с первым и последним переходами. В результате для всех 0 ≤ 𝑖 ≤ 𝑝 − 1 переход 
𝑢𝑖 будет заменен частью сети Петри, показанной на рисунке 2. Стрелка, входившая раньше в 
переход 𝑢𝑖, будет теперь входить в 𝑎𝑖,0, а выходившая из 𝑢𝑖 будет выходить из 𝑎𝑖,𝜏(𝑢𝑖)−1.

Передача данных через каналы будет производиться с помощью алгоритма Дейкстры 

для решения задачи о производителе и потребителе [6]. В этом алгоритме очередь канала при 
чтении и записи данных захватывается с помощью бинарного семафора. Отсюда следует, что 
запись в канал и чтение из него являются зависимыми действиями, в том смысле, что они не 
могут происходить одновременно.

Рис. 2. Измельчение i-ого перехода

Напомним определение трассы, введенное Мазуркевичем [7]. С этой целью рассмотрим 

параллельный вычислительный процесс, состоящий из операций, принадлежащих некоторому 
множеству команд E. Если операции могут выполняться одновременно, то будем называть их 
независимыми. В противном случае они зависимы. Историей [1] называется конечная 
последовательность операций. Для любого процесса, заданного с помощью конечной 
последовательности выполняемых операций мы можем переставлять выполнение рядом 
стоящих независимых операций – результат выполнения процесса не изменится. Поэтому 
можно отождествлять истории, полученные друг из друга с помощью таких перестановок. 
Классы историй, полученных с помощью описанного отождествления, называются трассами
[7].

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

6

http://naukovedenie.ru 56TVN114

Обработка 𝑛 элементов данных конвейером 𝑢0 … 𝑢𝑝−1 описывается трассой, состоящей 

из операций 𝑎𝑖,𝑗, 0 ≤ 𝑖 ≤ 𝑝 − 1, 0 ≤ 𝑗 ≤ 𝜏(𝑢𝑖) − 1, со временем выполнения 1:

(𝑎0,0𝑎0,1 ⋯ 𝑎0,𝜏(𝑢1)−1𝑎𝑝−1,1𝑎𝑝−1,2 ⋯ 𝑎𝑝−1,𝜏(𝑢𝑝−1)−1)

𝑛
,

в которой для каждого 𝑖
попарно зависимы операции 𝑎𝑖,0, 𝑎𝑖,1, … , 𝑎𝑖,𝜏(𝑢𝑖)−1,

принадлежащие 𝑢𝑖, а также для каждого 𝑖 из диапазона 0 ≤  𝑖 ≤  𝑝 − 2 зависимы операции
𝑎𝑖,𝜏(𝑢𝑖)−1 и 𝑎𝑖+1,0.

Полученная трасса является математической моделью для исследования всех

возможных историй асинхронного конвейера.

Всякой сети Петри соответствует асинхронная система (см. [8]). Ее состояниями служат 

маркировки. Операции определены переходами, действующими на маркировках с помощью 
срабатываний. Значит, можно воспользоваться результатами работы [8], в которой было
показано, что минимальное время обработки 𝑛 элементов данных будет равно высоте 
нормальной форме Фоаты этой трассы. Приведение трассы к нормальной форме Фоаты 
аналогично 
построению 
канонической 
ярусно-параллельной 
нормальной 
формы 
в 

терминологии [9].

В этой математической модели не участвует размер буферной памяти. Она строится из 

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

Описание компьютерной модели

При построении компьютерной модели мы ориентируемся на сеть Петри, показанную 

ниже. Местам будут соответствовать каналы c[0], c[1], …, c[p].

Рис. 3. Конвейер из p устройств

Компьютерная модель будет состоять из 𝑝 потоков (нитей). Они взаимодействуют с 

помощью операторов чтения из канала и записи в канал. Перед началом работы 𝑛 элементов 
входных данных записывается в канал c[0]. Затем загружаются потоки 0 ≤  𝑖 ≤  𝑝 − 1:

Thr(i)

{

int x;

for (int j=0; j<n; j++)

{

c[i]>>x; Sleep(tau[i]); c[i+1]<<x;

}

}

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

7

http://naukovedenie.ru 56TVN114

Здесь tau[i] равно 𝜏(𝑢𝑖). Пусть r[i] - число, равное времени чтения 𝑟(𝑐𝑖) из канала 𝑐𝑖, а 

w[i+1] - время записи 𝑤(𝑐𝑖+1) в канал 𝑐𝑖+1, 0 ≤  𝑖 ≤  𝑝 − 1.

Эти потоки будут работать параллельно. Синхронизация достигается с помощью класса 

канала.

Наша компьютерная модель имитирует многопроцессорную систему. Это становится 

возможным благодаря использованию подпрограммы Sleep(t), усыпляющей вызвавший ее 
поток на время t в миллисекундах. Мы проводили отладку программного обеспечения и 
испытания, используя процессор Intel(R) Core (TM) i3-2310M CPU. Заметим, что программная 
реализация возможна и на однопроцессорной системе. Но единица времени, с помощью 
которой мы считаем ускорение, в некоторых случаях должна увеличиваться. Например, для 
процессора Intel(R) ATOM(TM) CPU N270 эта единица времени должна быть равна 1 секунде, 
в этом случае аргумент для подпрограммы Sleep() надо умножить на 1000.

Класс канала состоит из циклической очереди, определенной как массив целых чисел.

Одна из программных реализаций этого класса и примеры использования приведены в учебном 
пособии [10].

Выполнение оператора c[i]>>x начинается с ожидания события «канал не пуст». Затем 

поток захватывает канал c[i], извлекает из него элемент и освобождает канал. Перед 
освобождением мы добавили оператор Sleep(r[i]).

Запись c[i+1]<<x состоит из ожидания «свободного места» в очереди канала c[i+1]. 

Затем поток захватывает канал c[i+1], записывает в него элемент, выполняет задержку 
Sleep(w[i+1]) и освобождает канал.

На экран выводятся графики ускорений, изображенные на рисунке 4. Графики, 

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

Гипотетическая формула для нахождения ускорения получена в предположении, что 

размер буферной памяти достаточно большой. Исследования графиков ускорения при 
различных размерах буферной памяти показывают, что все эти графики практически совпадают 
с гипотетическим. Следовательно, производительность асинхронного конвейера почти не 
зависит от размера буфера. На практике, скорость обмена с одним регистром выше, чем с 
массивом регистров. Отсюда можно сделать предположение, что асинхронные конвейеры, у 
которых каналы состоят из одного регистра, являются оптимальными, как для производства, 
так и для использования.

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

8

http://naukovedenie.ru 56TVN114

Рис. 4. Графики зависимости ускорений от объема входных данных

Компьютерную модель можно применять также для исследования других свойств

конвейера. Например, для явления пузырька, которое имеет место в случае кратковременного
замедления действия одного из устройств конвейера. В этом случае на графике ускорения 
появится скачок:

Рис. 5. Явление пузырька

Исследование волновых систем

Переход t сети Петри называется входным для места p, если 𝑝𝑜𝑠𝑡(𝑡)(𝑝) ≥ 1. В этом 

случае проводится стрелка от t к p. Он называется выходным для p, если 𝑝𝑟𝑒(𝑡)(𝑝) ≥ 1. В этом 
случае проводится стрелка от p к t. Сеть Петри называется ацикличной, если в ней нет
направленных циклов, состоящих из стрелок 𝑝0 → 𝑡0 → 𝑝1 → 𝑡1 → ⋯ → 𝑝𝑘 = 𝑝0.

Рассмотрим волновые системы [10]. Волновую систему можно рассматривать как

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

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

9

http://naukovedenie.ru 56TVN114

имеющего входной переход, равна некоторому числу 𝑛 > 0. Переходам соответствуют 
функциональные устройства, взаимодействующие через буферную память, находящуюся в 
местах. Термин “волновая” был введен в [11]. Мы рассмотрим в качестве примера волновую 
систему, имеющую следующую сеть Петри:

Рис. 6. Сеть Петри волновой системы

Входные данные размещаются в местах, имеющих один выходной переход. На рисунке

6 входные данные размещаются в каналах 𝑐0 и 𝑐1. Результаты вычислений записываются в 
каналы, соответствующие местам, имеющим по одному входному переходу. Для данного 
примера, этими каналами будут 𝑐6 и 𝑐7.

Компьютерная модель этой волновой системы состоит из потоков, соответствующих 

переходам ее сети Петри и каналов, соответствующим ее местам. Программная реализация 
использует описанный выше класс канала. Всякий поток, соответствующий переходу, состоит 
из цикла. В теле цикла сначала принимаются данные из входных каналов. Затем имитируется
выполнение операции с помощью подпрограммы Sleep(). После этого передаются данные в 
выходные каналы. Для волновой системы, показанной на рисунке 6, были получены следующие 
графики зависимости времени 𝑇5(𝑛) обработки n пар элементов входных данных, где n
изменяется от 1 до 99.

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

10

http://naukovedenie.ru 56TVN114

Рис. 6. Графики времени обработки для волновой системы

Время выполнения операций, которые задавались для функциональных устройств, 

приведены в таблице, первой строке соответствует самый нижний график, второй – следующий 
и т.д.

Времена обработки функциональных устройств

𝜏(𝑢0)
𝜏(𝑢1)
𝜏(𝑢2)
𝜏(𝑢3)
𝜏(𝑢4)

2
2
1
0
1

2
2
3
4
3

2
2
3
5
3

6
5
6
5
4

6
5
7
5
4

6
5
7
8
4

Были проведены эксперименты с другими волновыми системами. Во всех случаях 

графики хорошо приближаются прямым. На основании этого мы выдвигаем следующую 
гипотезу:

Для
всякой волновой системы, состоящей
из p
функциональных устройств,

существуют константы A и B, такие, что время обработки данных объема n, которые 
передаются через входные каналы волновой системы, можно вычислять по формуле 𝑇𝑝(𝑛) =
𝐴 + 𝐵(𝑛 − 1).

В этом случае константа A будет равна 𝑇𝑝(1), а 𝐵 = 𝑇𝑝(2) − 𝑇𝑝(1) . Очень возможно, что 

𝐵 = 𝑚𝑎𝑥0≤𝑖≤𝑝−1 𝜏(𝑢𝑖) . Доказательство этой гипотезы значительно облегчит расчет ускорения 
и производительности волновой системы.

Заключение

Результаты экспериментов позволяют сделать вывод о том, что построенная нами 

компьютерная модель асинхронного
конвейера с буферной памятью
подходит
для 

исследования поведения этого конвейера. Исследования привели к выводу, что объем 
буферной памяти не влияет на ускорение. Мы нашли также возможность моделирования 
явления пузырьков. Компьютерная модель была также обобщена нами для изучения волновых 
систем. Мы высказали и экспериментально подтвердили гипотезу о том, что для волновой 
системы график зависимости времени обработки данных от числа входных элементов
описывается с помощью прямой линии.