на главную ] 

Многомашинный вычислительный комплекс.

Евгений Борисов

21 октября 2000 г.


1 Введение

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

1.1 Управление

Проблема управления - имеет два основных решения: централизованное и распределённое, что соответствует системам типа SIMD и MIMD по известной классификаций Флинна.

1.2 Память

1.3 Связь

Связь между процессорами представляет собой наиболее сложную проблему и имеет много решений. Удобно различать универсальные и специальные системы связи.

2 Постановка задачи

Вычислительные системы сверхвысокой производительности стоят дорого. Но существует возможность объединить мощности нескольких PC для решения задач, требующих большой вычислительной мощности. В данной работе предлагается "дешевый суперкомпьютер". На аппаратной базе локальной сети строиться распределенная многопроцессорная система - мы объединяем несколько компьютеров в виртуальную многопроцессорную машину. Ниже предлагается автоматная модель и пример реализации такой виртуальной машины.

Рисунок 3: виртуальная многопроцессорная машина
\begin{figure}\centering
\begin{picture}(170,135)
% put(0,0)\{ rectangle\{170\}...
...t(80,35){\vector(0,-1){20}}
\put(60,7){результат}
\end{picture}\end{figure}

3 Описание модели

Предлагаемая модель состоит из автоматов двух типов:

Рисунок 4: схема модели
\begin{figure}\centering
\begin{picture}(260,170)
% put(0,0)\{ rectangle\{260\}...
...25){\huge$M_1$}
\put(70,35){\vector(1,0){40}}
}
\end{picture}\end{figure}

где

3.1 Вычислительный модуль


M = ( Z, V, R, α,β, z0 )

Рисунок 5: автомат-вычислитель
\begin{figure}\centering
\begin{picture}(180,40)
% put(0,0)\{ rectangle\{180\}\...
.../p$}
\put(75,30){$v_0/p$}
\put(70,5){$v_1,r/p$}
\end{picture}\end{figure}

3.2 Управляющий модуль


S = ( Q, X, D, f, g, Y, q0)

Рисунок 6: управляющий автомат
\begin{figure}\centering
\begin{picture}(320,160)
\put(30,0){
\put(0,129){
...
...
\put(265,110){\footnotesize$v_1/(v_1,\dots,v_1)$}
\end{picture}\end{figure}

Отдаем задание первому свободному вычислительному модулю. Если свободных нет, то ждем освобождения ресурсов (собираем результаты). v1 на вход - конец работы (собираем результаты).

4 Реализация

Рисунок 7: схема программной реализации
\begin{figure}\centering
\begin{picture}(250,245)
% put(0,0)\{ rectangle\{250\}...
...ераций\}
% put(195,228)\{ vector(0,-1)\{25\}\}
\end{picture}\par\end{figure}

4.1 Взломщик шифра

В этой работе предлагается простая система шифрования данных, которую можно отнести к классу симметричных криптосистем, и ''взломщик'' шифра. Процедура шифрования заключается в сложении по модулю 2 побайтно закрываемого текста и заданного пользователем ключа. Вскрытие кода осуществляется последовательным подбором ключа. Таким образом, количество необходимых для вскрытия итераций равно 2n, где n - размерность ключа. Например, при n = 24 (трехбуквенный ключ) необходимо произвести 16777216 итераций. Ключ такой длинны был использован при контрольных прогонах программы.

4.1.1 Результаты счета

Одна машина

Две машины

4.2 Вычисление числа $\pi $

Число $\pi $ будем вычислять как определенный интеграл :


\begin{displaymath}\int\limits_{0}^{1}{\frac{4}{1+x^2}}dx = \left. 4\cdot \arctg(x)\right\vert _0^1 = \pi\end{displaymath}

Согласно правилу прямоугольников интеграл можно заменить суммой:


\begin{displaymath}h \cdot \sum\limits_{i=1}^{n}\left(\frac{4}{1+x_i^2}\right)\end{displaymath}

где h = 1/n ; xi = ( i - 0.5 ) . h


4.2.1 Результаты счета

Одна машина

# pi.cl -i20000000

-=  PI calculation client (TCP) v.1 =-

------ PI servers --------
qnx_1:5041
--------------------------
connect to qnx_1:5041 ... ok
disconnect .............. ok
connect to qnx_1:5041 ... ok
disconnect .............. ok
-------------------------
time = 69 sec.
pi=3.141592753589926
#_

Две машины

# pi.cl -i20000000

-=  PI calculation client (TCP) v.1 =-

------ PI servers --------
qnx_1:5041
localhost:5041
--------------------------
connect to qnx_1:5041 ....... ok
disconnect .................. ok
connect to localhost:5041 ... ok
disconnect .................. ok
connect to qnx_1:5041 ....... ok
disconnect .................. ok
connect to localhost:5041 ... ok
disconnect .................. ok
--------------------------
time = 36 sec.
pi=3.141592753589926
#_


Исходные тексты программ


Литература

1
Ю.В.Капитонова, А.А.Летичевский ''Математическая теория проектирования вычислительных систем'' Москва,''Наука'',1988.

2
В.С.Михайлевич, Ю.В.Капитонова, А.А.Летичевский, И.Н.Молчанов,С.Б.Погребинский ''Организация вычислений в многопроцессорных вычислительных системах'' Кибернетика N3 1984.

3
В.С.Михайлевич,Ю.В.Капитонова, А.А.Летичевский ''О методах организации макроконвеерных вычислений'' Кибернетика N3 1986.

4
А.Е.Дорошенко ''Математические модели и методы организации высокопроизводительных параллельных вычислений'' Киев,''Наукова думка'',2000

5
В.В.Корнеев ''Параллельные вычислительные системы'' Москва,''Нолидж'',1999.

6
С.Баричев ''Криптография без секретов''.

7
А.Робачевский ''Операционная система UNIX'' Санкт-Петербург, ''bhv'', 1999.

8
Т.Чан ''Системное программирование на C++ для UNIX'' Киев, ''bhv'', 1999.

9
А.Колин ''Введение в операционные системы'' , Москва ''Мир'' 1975.

10
''Программирование на параллельных вычислительных системах'' под ред. Р.Бэбба II Москва, ''Мир'', 1991.


Evgeny S. Borisov
2005-03-15
Яндекс.Метрика
TOP.zp.ua PR-CY.ru
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.