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

•Э О,-, ^ о/

Оэ

, V САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

с\, ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Оу ---

На правах рукописи

Баталова Людмила Юрьевна

МЕТОД И СРЕДСТВА ДИАГНОСТИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ

Специальность: 05.13.13 - Вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1993

Работа выполнена в Санкт-Петербургском государственном электротехническом университете

Научный руководитель -кандидат технических наук КШЭДАРЕВ A.C.

Официальные оппоненты: доктор технических наук, профессор Яковлев В.В. кандидат технических наук, с.н.с. Данилов В.В.

Ведущая организация - ЦНШ "Гранит"

Защита диссертации состоится " " '^1993 г.

уГ^П0*

в часов на заседании специализированного совета

К 063.36.12 Санкт-Петербургского Государственного элекротех-нического университета по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно.ознакомиться в библиотеке университета.

-

:1

Автореферат разослан

„ 9 -

1993 г.

Ученый секретарь специализированного совета

Балакин В.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Создание вычислительных систем с массовым параллелизмом (ВСМП) является ключевой проблемой современного этапа развития науки и техники.

Основным способом достижения требуемой производительности вычислительных систем является использование распределенной и потоковой обработок в ВСМП, которые должны состоять из сотен и тысяч процессоров. Взаимодействие такого количества процессоров в виде М1Ш)-систем может быть организовано различными способами, но особое внимание уделяется системам с нетрадиционными динамическими архитектурами. Процессорные элементы могут динамически включаться и выключаться из конфигурации в процессе решения задачи, что создает условия как для повышения производительности и надежности, так и возникновения проблем, связанных с тестированием дефектов подобных ВСМП. Сложность организации тестового диагностирования (ТД) ВСМП обусловлена:

- сложностью самого объекта и его модели;

- параллелизмом вычислительных процессов;

- недетерминизмом назначения ресурсов;

- ограничениями на встроенную аппаратуру.

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

В настоящей работе предлагается подход в организации тестового диагностирования ВСМП на уровне процессов, основанный на развитии конструктивного метода в тестовом диагностировании.

Цель работы и задачи исследования. Целью диссертационной работы является разработка метода тестового диагностирования ВСМП на уровне процессов. Для достижения поставленной цели в

- г -

работе решались следующие основные задачи:

- разработка формальной модели объекта диагностирования (ОД), описывающая многоуровневую организацию ВСМП;

- формулировка базового набора свойств ОД на уровне процессов и их дефектов;

- формулировка набора свойств ОД на уровне процессов и их дефектов с учетом архитектурных особенностей потоковых ВО;

- определение отношений на множестве дефектов свойств;

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

Основные методы исследования. Для решения поставленных задач использовались понятия и метода теории вычислительных систем, теории множеств, математической логики, научного ана-' лиза и синтеза; в работе сочетаются формальный и содержательный подхода.

Научная новизна результатов, полученных в диссертационной работе, заключается в следующем:

- разработана диагностическая модель вычислительных систем с массовым параллелизмом, отличающаяся представлением ОД на уровне процессов и содержащая формальное описание объекта диагностирования и множебт-ёЪ:его дефектов в виде искажений свойств протоколов его функционирования;

- разработан метод ¿¡писания свойств вычислительных систем с потоковыми архитектурами, отличающийся учетом семантической связи уровней в многоуровневой модели ОД.

Практическая ценность работы. Значение результатов диссертационной работы для практики заключается в следующем:

- разработан способ построения тестов, основанный на выделении идентификаторов свойств протоколов функционирования ОД, их упорядочении и процедуре доказательства истинности;

- разработаны варианты структурной организации аппаратно-программной реализации диагностической подсистемы;

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

'' • Внедрение результатов работы. Основные результаты работы

используются в Институте проблем вычислительной техники Академии Наук Российской Федерации, г. Ярославль, .и в ЛИИАН, г. Санкт-Петербург.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

- Краевой научно-технической конференции молодых ученых, г. Красноярск, 1989-1990 гг.;

- 3-м Региональном семинаре "Распределенная обработка информации", г. Улан-Уде, 1989 г.;

- Межреспубликанской конференции молодых ученых, г. Саранск, 1989 г.;

- Областной научно-технической конференции, г. Оренбург, 1989 г.;

- Международной конференции "Искусственный интеллект -промышленное применение", г.- Ленинград, 1990 г.;

- Всесоюзной школе-семинаре "Диагностика, надежность, неразрушащий контроль электронных устройств и систем", г. Владивосток, 1990 г.;

- Научно-технических конференциях профессорско-преподавательского состава ЛЗТИ им. В^.-Ульянова (Ленина) (г.Ленинград, 1939-1990 гг.).

Публикации. По материалам диссертации опубликовано 12 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав с выводами, заключения, списка литературы, включающего 116 наименований, и 2 приложений. Основная часть работы изложена на 162 страницах машинописного текста. Работа содержит 10 таблиц и 26 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ '

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

В первом разделе диссертационной работы рассматривается

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

При использовании известных методов ТД для решения задач диагностирования ВВС приходится сталкиваться со следующими ограничениями:

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

- процедурностыо метода (как правило, модель задается перечислением возможных отказов в цепях системы);

- большим размером теста (методы, применяемые на вентильном и функциональном уровнях, строят тесты, общий объем которых связан кубической зависимостью с количеством компонент; кроме того, тесты не являются минимальными).

Введение уровня процессов рассматривается как средство отражения особенностей распределенных ВС, таких как асинхрон-ность, параллелизм, недетерминизм трасс вычислений, что проявляется в формальной модели ОД введением предикатов второго порядка. "'

Модель объекта на уровне процессов задается в виде формул логики предикатов и временных интервальных отношений. Возможность перехода на нижние уровни определяется заданием семантики процессов. Дефекты ОД определяются через дефекты свойств протоколов функционирования ВС. Под "протоколом" в работе понимается описание взаимодействия процессов, которые в виде асинхронных автоматов образуют некоторый "коллектив вычислителей", выполняющий задачу.

,--12 втором разделе диссертационной работы рассматривается формальная модель объекта диагностирования на уровне процессов.

Построение формальной модели ОД на уровне процессов требует решения проблемы выбора формального аппарата для описа-

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

С формальной точки зрения для некоторой сложной euerem s, предотавимой в виде N-ки: ®=<к1,...где K1f...,K -

категории, относящиеся к системе s, можно задать некоторое

#

описание в виде высказываний некоторого языка iL, ilsP ,

Р*=СР.....Р ,...} - множество слов в алфавите п^*...*»^. В

настоящей работе описание системы задается в терминах высказываний языка логики предикатов и временных интервальных отношений между парами процессов А^А^ из множества процессов д.

Интервальные временные отношения г^А^А ) являются двухместными и интерпретируются как различные варианты расположения временных интервалов выполнимости процессов А± и А^. При этом некоторая последовательность взаимодействия процессов называется протоколом функционирования системы s. Каждый протокол задается своим синтаксическим и семантическим описаниями, определенными в виде формуд,. временной интервальной логики и логики предикатов.

Таким образом, диагностическая.модель определена двойкой ДМ=<МО, ВД>, где МО = <<и, д, 1> - " модель объекта включает множество к объектов, д процессов и ,.8 описаний протоколов функционирования системы, МД = <<и',д".ihr* > - модель дефектов включает множество ч' дефектных объектов, а' процессов, Я' описаний и ¡RR' свойств функционирования системы.

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

- б -

токолов функционирования системы, которые отражают важные критерии функционирования вычислительных систем.

Исходя из этого соображения, в МД было введено множество 1РК' дефектов свойств (Рг±, 1=1+9):

Рг1 - безопасности функционирования;

Рг2 - живучести;

Рг3 - взаимного исключения;

Ргд - частичной корректности;

Рг5 - ограниченности;

РГ6 - отсутствия неопределенности состояний;

Рг7 - отсутствия переспецификации;

Рг0 - полноты;

О

Ргд - отсутствия блокировок.

Это множество выбрано на основе анализа различных требований, предъявляемых к бездефектному функционированию' ВСМП. Определения свойств являются высказываниями, использующими предикаты временной интервальной логики и логики предикатов первого и второго порядков. Свойство называется выполнимым, если доказуемо высказывание: ?г , где Рг± - определение 1-го свойства. Если доказуемо обратное: )-"1Рг1, то свойство называется дефектным. --«ше"

Так, например, свойст§о2живучести гласит: "Система обладает этим свойством, если в процессе функционирования в соответствии с одним из свои^ протоколов, она в конце концов достигает желаемого конечного состояния, т.е. существует протокол функционирования системы, который содержит желаемые комбинации совместно .-выполняемых процессов". Графически это свойство можно ицтерпретировать как необходимость существования в ресурсам графе параллельной вычислительной системы с динамическим -назначением ресурсов Н-типов хотя бы по одной вершине-ресурсу каждого типа для того, чтобы граф-схема вычислений могла быть отображена на ресурсный граф и выполнена до конца. .,

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

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

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

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

В соответствии с работами в области исследования потоковых архитектур, которые ведутся в течение ряда лет на кафедре ВТ С.-ПБ.ГЭТУ, условие готовности команда к выполнению можно записать в виде конъюнкции условий наличия запросов, данных, ресурсов и директивного сигнала. Исходя из описания форматов команд, для описания различных стратегий управления были определены семантические описания процессов, включающие предикаты, характеризующие;

- выполнение команды с заданным кодом операции;

- наличие векторов запросов0от'источников и к приемникам; : •

- сигналы готовности, занятия й; освобождения ресурсов;

- сигналы готовности данных и формирования результата;

- директивные сигналы.

Имея описание семантики процессов', :были даны определения свойств и их дефектов для ВС с потоковыш'архитвктураш, отличающимися по типу используемой схемы вычислений: потоковой; потоково-запросной; потоково-ресурсной; пото'ково-запросно-ресурсной.

Построены синтаксические и семантические описания протоколов функционирования для элементарных схем всех" четырех типов, из которых можно строить произвольные схемы.1 -

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

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

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

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

Основой различных алгоритмов тестирования дефектов свойств является определение истинности соответствующих идентификаторов .

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

Выбранный метод обхода дерева тестов определяет стратегию тестирования "по горизонтали" или "по вертикали".

Также в третьем разделе рассмотрены вопросы организации диагностического процессора, 'реализующего предлагаемый метод многоуровневого тестирования^'- !

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

Вопросы организации тестирования алгоритмического и нижних уровней уже решены в рамках конструктивного направления.

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

В четвертом разделе результаты второго и третьего разделов объединены в методику построения тестов дефектов свойсв ВСМП на уровне процессов. Указанная методика продемонстрирована на примере решения задачи диагностирования потоковой ВС.

Методика построения тестов дефектов включает следующие этапы:

1° - концептуальный выбор диагностируемых свойств ВСМП;и стратегий тестирования;

2° - определение набора тестовых задач;

3° - описание синтаксиса и семантики протоколов тестовых задач;

4° - задание формул диагностируемых свойств;

5° - преобразование формул и задание идентификаторов;

6° - генерация тест-программы;

7° - запуск гест-программы, оценка качества теста;

8° - уточнение знаний о семантике ОД, переход либо к процедуре 3, либо - останов.

Для иллюстрации предложенного метода была разработана программная модель ВС с потоковой архитектурой и программной системой тестового диагностирования.

Модель объекта диагностирования, записанная в виде правил на языке PROLOG, представляет собой базу знаний об объекте.

Модуль тестирования свойств для доказательства их истинности формирует запросы в виде .логических высказываний к модели объекта для установления groi состояния.

Выполнено тестирование программной модели с целью установления истинности заданных свойств, протоколов функционирования рассматриваемой ВС. Рассмотрено влияние специально внесенных дефектов на различных -уровнях на истинность тестируемых свойств. Показано, что любые физические дефекты структуры моделируемой ВС проявляются в искажениях свойств. Тестирование на уровне процессов .позволяет сжимать диагностическую информацию в интегральные-.^оценки качества функционирования ОД. Многоуровневость полученных знаний позволяет генерировать тесты на различных- уровнях и обеспечивать тесты поиска дефектов с требуемой глубиной.

В заключении дается перечень основных полученных-'научных и практических результатов. , ~~

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В результате проведенного исследования были получены следующие результаты:

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

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

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

4. Впервые предложены варианты структурной организации аппаратно-программной реализации диагностической подсистемы на базе1 механизма логического вывода для реализации процедур тестирования дефектов свойств.

; 5. Разработана программная модель вычислительной системы с "потоковой архитектурой и программная система тестового диагностирования для моделирования процесса тестирования де-

фектов свойств протоколов функционирования ОД. Проанализирована связь между дефектами на уровне процессов и дефектами на нижних уровнях.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Баталова Л.Ю., Баталов Д.И., Иванов C.B. Управляющие вычислительные системы с векторно-потоковой архитектурой // Методы и средства управления технологическими процессами. Тезисы докладов межресп. научной конференции.- Саранск,1989.-С. 55.

2. Баталова Л.Ю., Баталов Д.И., Шарков А.Ю. Организация системы памяти векторно-потоковой вычислительной системы // Тезисы докладов краевой научно-технической конференции.-Красноярск,1989.- С. 40-41.

3. Баталова Л.Ю., Баталов Д.И., Шарков А.Ю. Модель параллельной машины логического вывода // Тезисы докладов областной научно-технической конференции.- Оренбург, 1989,- С. 75.

4. Баталова Л.Ю., Водяхо "А.И., Иванов C.B., Липецкая Н.Д. Методы и средства штеллйй'уальной диагностики сверхвысокопроизводительных вычислительных систем // Деп. в ВИНИТИ 14.02.89, N. 937-В89.- 27 с. ЛениГ^электр. техн. ин-т.

5. Баталова Л.Ю., Календарев" А. С'. Развитие концепции многоуровневого тестирования // В сб.' науч. трудов ДЦНТП -Л., 1991.

6. Баталова Л.Ю., Календарев A.C.,:-Липецкая Н.Д. Диагностика вычислительных систем на системном'уровне // В кн.: Распределенная обработка информации. Материалы краткосрочного семинара 10-17 имя / Под ред. Мухопада В.Н. >- Новосибирск, 1989.- 70 с.

7. Баталова Л.Ю., Календарев A.C., Липецкая Н.Д. Интеллектуальный сервис сверхвысокопроизводительных вычислительных систем // Структура и математическое обеспечение специализированных вычислительных комплексов.- Сб. науч. тр.- (Изв. Ленингр.электр.техн. ин-та ), Вып. 423.- Л., 1990.- С. 68-74.

8. Баталова Л.Ю., Календарев A.C., Липецкая Н.Д. Стратегия тестирования вычислительных систем с нетрадиционными архитектурами // В кн.: Диагностирование, надежность, неразру-шающий контроль электронных устройств и систем - Владивосток, 1990.- С. 75.

9. Баталова Л.Ю., Липецкая Н.Д. Недетерминированный алгоритм управления тестированием параллельных вычислительных систем // Молодые ученые и студенты - ускорению научнотехни-ческого прогресса в области радиоэлектроники и вычислительной техники.- Сб.докл., - Красноярск, 1989.- С. 35-36.

10. Баталова Л.Ю., Липецкая Н.Д. Построение системы продукций на языке интервальной логики для тестирования высокопроизводительных ВС // Структура и математическое обеспечение специализированных вычислительных комплексов.- Сб. науч. тр. (Язв. Ленингр. электр. техн. ин-та ), Вып. 436.- Л., 1991.-С. 56-62.

11. Водяхо А.И., Емелин В.П., Календарев A.CI, Липецкая Н.Д., Баталова Л.Ю. Интеллектуальный сервис для вычислительных систем с нетрадиционными архитектурами // Препринт Научного центра по фунд. пробл. выч. техн., ИПВТ АН СССР, N 13, - Ярославль, 1990.- 43 с.

12. Batalova L., Kalendarev A., Lipetskaja Ы., PuzanKov В., Vodjaho A. A Testing Approach for High Performance Computer Systems // (Reference N 257-P), PAKC0M-90, December 1011, 1990, Centre for development of advanced computing, Poone University Campus, India, pp. 53-57.