Разработка и исследование методов организации параллельно-конвейерных систем массового ввода тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Хашковский, Валерий Валерьевич

• Хашковский, Валерий Валерьевич
• кандидат технических наук
• 2002

Оглавление диссертации кандидат технических наук Хашковский, Валерий Валерьевич

ВВЕДЕНИЕ.•.

1. РАЗРАБОТКА ТЕХНОЛОГИИ МАССОВОГО ВВОДА ДОКУМЕНТОВ.

1.1. ИССЛЕДОВАНИЕ ЗАДАЧ МАССОВОГО ВВОДА.

1.1.1. ВВОД БЛАНКОВ.

1.1.2. ВВОД ЛИНЕЙНОГО ТЕКСТА.

1.2. ЭТАПЫ МАССОВОГО ВВОДА.

1.2.1. ЭТАП СКАНИРОВАНИЯ.

1.2.2. ЭТАП ПОВЫШЕНИЯ КАЧЕСТВА.

1.2.3. ЭТАПЫ СЕГМЕНТАЦИИ И РАСПОЗНАВАНИЯ.

1.2.3.1. СЕГМЕНТАЦИЯ.

1.2.3.2. РАСПОЗНАВАНИЕ.

1.2.4. ЭТАП ВЕРИФИКАЦИИ.

1.2.4.1. ГРУППОВАЯ ВЕРИФИКАЦИЯ.

1.2.5. ЭТАП ЭКСПОРТА.

1.2.6. ОЧЕРЕДИ ВВОДА ДОКУМЕНТОВ.

1.3. АРХИТЕКТУРА СИСТЕМ МАССОВОГО ВВОДА.

1.3.1. СТРУКТУРА СИСТЕМЫ МАССОВОГО ВВОДА.

1.3.2. ФУНКЦИОНИРОВАНИЕ СИСТЕМЫ МАССОВГО ВВОДА.

1.4. ПОСТАНОВКА ЗАДАЧИ.

1.5. ВЫВОДЫ ПО ГЛАВЕ.

2. АЛГОРИТМЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ В СИСТЕМАХ МАССОВОГО ВВОДА.

2.1. ПАРАЛЛЕЛИЗМ И КОНВЕЙЕРИЗАЦИЯ В ЗАДАЧАХ МАССОВОГО ВВОДА

2.1.1. ПАРАЛЛЕЛИЗМ ЭТАПОВ МАССОВОГО ВВОДА.

2.1.2. КОНВЕЙЕРИЗАЦИЯ ЭТАПОВ МАССОВОГО ВВОДА.

2.1.3. ДИАГРАММА РАСПРЕДЕЛЕНИЯ И НАЗНАЧЕНИЕ ЗАДАЧ МАССОВОГО ВВОДА.

2.2. ЗАДАЧИ М - И А-КЛАССОВ.

2.3. ИССЛЕДОВАНИЕ АЛГОРИТМОВ НАЗНАЧЕНИЯ ЗАДАЧ.

2.3.1. ИССЛЕДОВАНИЕ АЛГОРИТМОВ НАЗНАЧЕНИЯ ЗАДАЧ.

2.3.2. ЗАДАЧА НАЗНАЧЕНИЯ РАБОТ В УСЛОВИЯХ СИСТЕМЫ МАССОВОГО ВВОДА В ПРЕДЕЛАХ ОДНОГО ЭТАПА ОБРАБОТКИ.

2.4. РАЗРАБОТКА АЛГОРИТМА РАСЧЕТА ОКОНЧАНИЯ РАБОТ В СИСТЕМЕ МАССОВОГО ВВОДА ПРИ ОБРАБОТКЕ ОДНОРОДНЫХ ЗАДАЧ.

2.4.1. НАЧАЛЬНЫЙ РАСЧЕТ.

2.4.2. ДОБАВЛЕНИЕ СТАНЦИЙ.

2.4.3. УДАЛЕНИЕ СТАНЦИЙ.

2.4.4. ДОБАВЛЕНИЕ/УДАЛЕНИЕ ЗАДАНИЙ.

2.4.5. СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА АНАЛИТИКО-ИМИТАЦИОННОГО АЛГОРИТМА РАСЧЕТА ОКОНЧАНИЯ РАБОТ.

2.5. ВЫВОДЫ ПО ГЛАВЕ.

3. МЕТОДЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ОБРАБОТКИ В СИСТЕМАХ МАССОВОГО ВВОДА.

3.1. ВХОДНОЙ ПОТОК И ОБРАБОТКА В СИСТЕМАХ МАССОВОГО ВВОДА

3 .2. МНОГОЭТАПНАЯ ОБРАБОТКА В СИСТЕМАХ МАССОВОГО ВВОДА.

3.3. ПАКЕТНАЯ ОБРАБОТКА.

3.3.1. ПАКЕТНАЯ ОБРАБОТКА С ОДНОЙ ВЫДЕЛЕННОЙ СТАНЦИЕЙ НА КАЖДОМ ЭТАПЕ.

3.3.2. ПАКЕТНАЯ ОБРАБОТКА С ПРОИЗВОЛЬНЫМ ЧИСЛОМ ВЫДЕЛЕННЫХ СТАНЦИЙ НА КАЖДОМ ЭТАПЕ.

3.4. КОНВЕЙЕРНАЯ ОБРАБОТКА.

3.4.1. КОНВЕЙЕРНАЯ ОБРАБОТКА С ОДНОЙ ВЫДЕЛЕННОЙ СТАНЦИЕЙ НА КАЖДОМ ЭТАПЕ.

3 .4.2. КОНВЕЙЕРНАЯ ОБРАБОТКА С ПРОИЗВОЛЬНЫМ ЧИСЛОМ ВЫДЕЛЕННЫХ СТАНЦИЙ НА КАЖДОМ ЭТАПЕ.

3 .5 СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА МЕТОДОВ ОРГАНИЗАЦИИ ОБРАБОТКИ В СИСТЕМАХ МАССОВОГО ВВОДА.

3.6. ВЫВОДЫ.

4. ОПТИМИЗИРОВАННАЯ ОБРАБОТКА И ОЧЕРЕДИ В СИСТЕМАХ МАССОВОГО ВВОДА.

4.1. ОЧЕРЕДИ.

4.2. ПАКЕТНАЯ ОБРАБОТКА БЕЗ ЗАКРЕПЛЕНИЯ СТАНЦИЙ.

4.3. СЛИЯНИЕ АВТОМАТИЧЕСКИХ ЭТАПОВ.

4.4. ВЫВОДЫ.

5. РАЗРАБОТКА КОМПЛЕКСА ПРОГРАММНЫХ СРЕДСТВ УПРАВЛЕНИЯ РЕСУРСАМИ СИСТЕМ МАССОВГО ВВОДА.

5.1. СОСТАВ И СТРУКТУРА КОМПЛЕКС А.

5.2. ОЧЕРЕДЬ ВВОДА ДОКУМЕНТОВ И МАРШРУТЫ ОБРАБОТКИ.

5.3. СИНХРОНИЗАЦИЯ И КЭШИРОВАНИЕ.

5.4. СЕРВЕР.

5.5. КЛИЕНТ.

5.6. ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов организации параллельно-конвейерных систем массового ввода»

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

Актуальность темы.

В последние годы наиболее актуальными для всего человечества в целом являются вопросы, связанные с переходом на безбумажные технологии. Один из фундаментальных этапов этого перехода состоит в массовом переводе бумажных документов в их компьютерные эквиваленты. Такой перевод осуществляется в два этапа. Сначала документы сканируются, а затем решается проблема формирования их компьютерного эквивалента. Решение этой проблемы сопряжено с проблемой распознавания образов, в частности, распознавания символов, которая не имеет удовлетворительного однозначного решения. Для оптического распознавания символов имеются широко известные программные средства такие, как OmniPage, CuneiForm, FineReader, Kadmos и др., каждое из которых обладает своими достоинствами и недостатками как по параметрам скорости распознавания, так и по качеству результата, а также по областям применимости. Так, например, FineReader реализует средства распознавания бланков, но не поддерживает разделяемых библиотек, a Kadmos позволяет включать библиотеки распознавания в производимое программное обеспечение, однако ограничен поддержкой одного языка и не позволяет использовать на этапе распознавания словарные статьи. При этом все существующие подходы к решению задачи распознавания и их реализации достаточно трудоемки в плане вычислительных затрат. Так, время оптического распознавания одного листа на компьютере типа Pentium III 800 MHz составляет от 10 до 30 секунд, а скорость сканирования на современном оборудовании достигает 200 листов в минуту. Это различие обуславливает необходимость исследование и разработки способов повышения быстродействия систем, основанных на использовании технологий различного быстродействия.

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

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

Вопросы организации параллельно-конвейерных вычислительных систем давно привлекают ученых с точки зрения архитектур и средств управления ресурсами параллельно-конвейерных систем. Значительное развитие в нашей стране получила концепция однородных вычислительных структур, сформулированная в 1962 г. [44, 45] в Институте математики СО АН СССР, а также программное обеспечение однородных вычислительных систем [62]. Развивались и вопросы организации структуры и функционирования многомашинных, многопроцессорных, магистральных (конвейерных), матричных, векторных, ассоциативных систем, а также систем с ансамблем процессоров, с комбинированной и перестраиваемой структурой [37].

Не меньшее внимание исследователей направлено на разработку математического обеспечения для вычислительных систем и средств разработки. В связи с развитием параллельных вычислительных систем и программирования для них, возник термин [40] «параллельное программирование». Построение параллельных систем, вычислительных систем, объединенных сетью передачи данных, и программного обеспечения к ним привело к исследованию вопросов анализа, планирования и диспетчирования процессов выполнения программ параллельно-конвейерными системами различных конфигураций и в различных прикладных областях. Большое научное и практическое значение имеют работы Поспелова Д.А. [73], Хорошевского В.Г. [46, 86, 106, 107], Евреинова Э.В. [44-46], Косарева Ю.Г. [62], Прангишвили И.В. [75], Танаева B.C. [98], Гузика В.Ф. [126], Каляева A.B. [127], Пьявченко О Н., Бурцева B.C. [125], Чефранова А.Г. [6-8, 84, 108-Ш], Макаревича О.Б. [5-7], Барского А.Б. [10-14], Маматова Ю.А. [69], Панишева A.B. [24, 25, 71], Головкина Б.А. [36-38], Грэхэма P.JI. (Graham R.L.) [123], Максименкова A.B. [66-68], Канцедала С.А. [56], Варакина A.C. [23], Сотскова Ю.Н. [93], Пашкеева С.Д. [72], Вахания H.H. [26].

В качестве аппаратного базиса для организации сетевого параллельно-конвейерного вычислительного процесса для обеспечения массового ввода используется локальная вычислительная сеть (ЛВС), обеспечивающая с точки зрения структуры информационных связей полный граф. Как известно, такая структура связей между вычислителями является наиболее подходящей для построения однородных вычислительных систем [46]. Существует несколько способов объединения компьютеров в сеть — топологий построения сетей, отличающихся по таким параметрам, как пропускная способность, надежность, живучесть и др. Достаточно подробно топологии рассматриваются в [100]. Наиболее распространены звездообразная, кольцевая и шинная топологии. В последнее время при проектировании и модернизации существующих вычислительных сетей происходит переход на иерархические структурированные кабельные системы на основе витой пары пятой категории, обеспечивающие пропускную способность до 100 Мбит/сек. и обладающие хорошими показателями живучести. Так при выходе из строя некоторого узла, вся остальная сеть остается работоспособной, а при поломке сетеобразующего оборудования нарушается работа только устройств, зависящих непосредственно от неисправного устройства. Большое разнообразие параметров, влияющих на работу вычислительных сетей различных топологий, качественные изменения эффективности функционирования сетей в зависимости от масштабов, необходимость использовать различные по характеристикам протоколы взаимодействия определяют интерес исследователей в этой области [60, 61, 63, 68, 74, 80, 92, 102, 114, 116]. Исследованию подвергаются как структура сети [28, 51, 54], так и обслуживание в сети [47], обработка и передача данных [49, 53], оптимизация размещения данных [50, 58, 81], протоколы обмена [18, 20, 43, 48, 77, 87, 88]. Вопросы измерения характеристик сетей рассмотрены в [9]. Исследуются также вопросы информационной безопасности в сетях [70].

Современные технологии разработки программного обеспечения базируются на принципах повторного использования кода. Такой подход сопряжен с использованием специализированных технологий, следование которым предоставляет разработчику возможность использовать функциональность стороннего программного обеспечения. Наиболее показательна в этом плане операционная система Windows, позволяющая реализовать технологии COM/DCOM, производства фирмы Microsoft. Используя СОМ-технологию, разработчик имеет возможность затрачивать минимальное количество усилий на организацию, например, пользовательского интерфейса текстового редактора. Поскольку такая задача не является центральной, достаточно, используя СОМ-технологию, загрузить соответствующий СОМ-сервер и воспользоваться его функциональностью в своем приложении, уделив при этом максимум внимания решению основной проблемы. Существуют и другие аналогичные технологии. Так, хорошие показатели по производительности имеет CORBA, менее известны PVM и DCE и некоторые другие.

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

Следует заметить, что переход на безбумажные технологии практически не ограничивается только задачами сканирования и распознавания. Зачастую сканируемые документы имеют невысокое качество печати или задолго до сканирования пылятся в архиве. Характеристики оборудования сканирования (сканера) со временем ухудшаются. Поэтому перед проведением распознавания желательно производить графическую обработку изображений документов для коррекции качества сканирования и устранения помех, присущих оригинальному изображению. Кроме того, многие задачи автоматизированного ввода не могут быть решены только использованием программных средств. Так, например, при обработке документов высокой важности необходимо использовать операторский труд для проверки (верификации) результатов распознавания, для сегментации текста и др. То есть, при реализации системы массового ввода документов необходимо использовать многоэтапный, человеко-машинный процесс обработки каждого отсканированного листа. Также необходимо учитывать, что разные листы могут обрабатываться с использованием разных этапов обработки, ведь совершенно очевидно, что экзаменационные бланки и литературные источники для перевода в компьютерный вид должны быть обработаны по-разному.

Широкая область применения систем массового ввода и высокая степень актуальности инициировали создание в ТРТУ Южно-Российского Центра Сканерных Технологий и Сертификации (ЮРЦ СканТех) на базе Международной лаборатории ELDIC (Educational Labor for Distance Information Communications) и Ростовского областного центра новых информационных технологий (РОЦ НИТ).

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

Цель диссертации.

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

Для достижения поставленной цели были решены следующие задачи:

1. Исследование и разработка состава технологии массового ввода, разработка классификации задач массового ввода, этапов их обработки.

2. Исследование возможности организации параллельно-конвейерной обработки в системах массового ввода.

3. Разработка и исследование алгоритма расчета окончания работ в пределах одного этапа обработки.

4. Разработка и исследование методов расчета системы массового ввода в пределах нескольких этапов обработки.

5. Разработка и исследование методов расчета системы массового ввода с учетом очередей к этапам обработки.

6. Разработка средств программной поддержки параллельно-конвейерной обработки в системе массового ввода.

Методы исследования.

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

На защиту выносятся.

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

1. Архитектура систем массового ввода.

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

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

4. Средства программной поддержки параллельно-конвейерной обработки в системе массового ввода.

Практическая ценность.

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

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

Теоретические и практические результаты работы использованы при выполнении госбюджетной НИР «Разработка новых моделей и алгоритмов нечеткого ситуационного анализа и создание на их основе интеллектуальных гибридных систем принятия решений и управления».

Разработанная система организации параллельно-конвейерного вычислительного процесса в системе массового ввода внедрена в ЮжноРоссийском Центре Сканерных Технологий и Сертификации (ЮРЦ СканТех), и использована при проведении аттестационного и абитуриентского тестирования в ТРТУ в 2001 г., а также для обработки результатов вступительных испытаний ТРТУ в 2001 г.

Материалы диссертационной работы использованы в курсах кафедры математического обеспечения и применения ЭВМ факультета автоматики и вычислительной техники: «Теория вычислительных процессов», «Операционные системы», а также при постановке авторского курса «Системы безбумажного документооборота» в рамках переподготовки специалистов на факультете.

Исследования проводились в рамках работ Международной лаборатории ELDIC по программе DAAD "Leonhard Euler" в 1998-2000г.

Апробация результатов работы.

Основные результаты диссертационной работы неоднократно докладывались и обсуждались на конференциях и семинарах ТРТУ, НКБ МИУС в том числе:

Научно-технические конференции профессорскопреподавательского состава ТРТУ (Таганрог, ТРТУ, 2000,2001 гг.)

Конференция с международным участием «Компьютерные технологии в управленческой и инженерной деятельности» (Таганрог, МИУС, 2000г.)

Всероссийские конференции студентов и аспирантов (Таганрог, ТРТУ, 1999,2000 гг.)

3-я Всероссийская научная конференция молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения». (Таганрог, 2000.)

Публикации.

По материалам работы опубликовано 8 печатных работ [29-33, 103105]. Материалы диссертации использовались в заключительном отчете по НИР [32].

Структура и объем диссертации.

Диссертация состоит из введения, пяти разделов, заключения и приложений, текст изложен на 137 страницах, содержит 22 рисунка, 2 таблицы, список литературы из 127 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Хашковский, Валерий Валерьевич

Результаты работы внедрены в Южно-Российском Центре Сканерных Технологий и Сертификации и использованы для создания электронной библиотеки докторских диссертаций, проведения абитуриентского и аттестационного тестирований в ТРТУ в 2001 г., а также при обработке результатов вступительных испытаний ТРТУ в 2001 г.

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

ЗАКЛЮЧЕНИЕ

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

Основные теоретические и практические результаты состоят в следующем:

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Хашковский, Валерий Валерьевич, 2002 год

1. Бакенрот В.Ю. Алгоритмы функционирования неоднородных вычислительных систем.—Автоматика и вычислительная техника, 1981, № 1, с.64-65.

2. Бакенрот В.Ю. Исследование и разработка алгоритмов оперативного диспетчирования задач в многопроцессорных системах пакетного типа. — Дисс. канд. техн. наук, Таганрог: ТРТИ, 1978. — 178 с.

3. Бакенрот В.Ю. Об эффективности одного алгоритма построения расписания. — Кибернетика, 1980, № 1, с. 140—143.

4. Бакенрот В.Ю. Эффективность алгоритмов планирования в сетях мультипроцессоров. Известия АН СССР, Техническая кибернетика, 1985, № 1, с. 62-71.

5. Бакенрот В.Ю., Макаревич О.Б. Два алгоритма диспетчирования задач для однородных вычислительных систем.—В кн.: Гибридные вычислительные машины, Киев, 1977, с. 160-163.

6. Бакенрот В.Ю., Макаревич О.Б., Чефранов А.Г. О верхних границах ЬРТ-расписаний. — Известия СКНЦ ВШ. Технические науки, 1983, №4.

7. Бакенрот В.Ю., Макаревич О.Б., Чефранов А.Г. О числе прямоугольников единичной ширины, достаточном для упаковки заданных прямоугольников. — Кибернетика, 1984, № 1, с. 26-27, 32.

8. Бакенрот В.Ю., Чефранов А.Г. О качестве списковых диспетчеров,—Кибернетика, 1988, № 3, с. 118-119

9. Бакланов И.Г. Технология измерений в современных телекоммуникациях -М.ЭКО-ТРЕНДЗ, 1998

10. Барский А.Б. Автоматическое распределение работ между двумя вычислительными устройствами одинаковой производительности. — Известия АН СССР. Техническая кибернетика, 1968, №4, с. 32—38.

11. Барский А.Б. Минимизация числа вычислителей при реализации вычислительного процесса в заданное время.—Известия АН СССР. Техническая кибернетика, 1968, №6, с.69-74.

12. Барский А.Б. О построении диспетчеров для вычислительных систем.—Известия АН СССР. Техническая кибернетика, 1971

13. Барский А.Б. Параллельные процессы в вычислительных системах: планирование и организация -М.:Радио и Связь, 1990

14. Барский А.Б. Планирование параллельных вычислительных процессов -М.Машиностроение, 1980

15. Блинова JIM., Пьявченко О.Н. Синтез структуры специализированной вычислительной системы с ярусно-конвейерной обработкой информации по критерию баланса времени. — Электронное моделирование, 1991, т. 13, N2, с. 99—101.

16. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ -М.Энергоатомиздат, 1984

17. Бондаренко А.Т., Сапатый П.С. Алгоритм распределения независимых работ на параллельно работающие устройства.—Известия АН СССР. Техническая кибернетика, 1975, №4, с.101-103.

18. Борец Б.Ю. Исследование и разработка программно-аппаратных средств построения территориальных сетей интегрального обслуживания, Диссерт. к.т.н -Таганрог, 1999

19. Бусленко Н.П, Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем, —М.:Советское радио, 1973

20. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ -М.Финансы и Статистика, 1981

21. Вайрадян A.A., Коровин A.B., Удалов В.Н. Эффективное функционирование управляющих вычислительных систем,—М.:Радио и связь, 1984. -328 с.

22. Валаев Г.Н. и др. Реконфигурируемая вычислительная среда в интеллектуальной системе управления автономным ЛА. — Известия РАН. Теория и системы управления, 1995, № 4, с.234-245.

23. Варакин A.C. Эффективные алгоритмы в системе управления гибким автоматизированным участком металлообработки.— Дисс. канд. техн. наук, Харьков: ХАДИ, 1990. 147 с.

24. Варакин A.C., Данильченко A.M., Панишев A.B. Решение задачи о назначении работ на процессоры двухуровневой системы.— Кибернетика, 1988, №2. с.58-62.

25. Варакин A.C., Панишев A.B. Анализ алгоритма распределения ресурсов в двухстадийной вычислительной системе.—Автоматика и вычислительная техника, 1990, N 4, с. 57-58.

26. Вахания H.H. Распределение заданий для параллельных машин с разным быстродействием. -Автоматика и Телемеханика, 1995, № 2, с. 155 163.

27. Венкова Н.Б., Тушкина Т.А., Шахбазян К.В. О расписании, минимизирующем число процессоров однородной вычислительной системы.—Известия АН СССР. Техническая кибернетика, 1971, №5, с.115-117.

28. Верма П. Сети связи ЭВМ. Оценка эффективности функционирования. Структурный анализ., пер. с англ. -М:Радио и Связь, 1992

29. Вишняков Ю.М., Хашковский В.В. Организация вычислительного процесса в сканцентре—Материалы конференции с международным участием "Научная сессия МИФИ-2001"

30. Вишняков Ю.М., Хашковский В.В. Параллельная диспетчеризация заданий в составе сканцентра.—Таганрог: Известия ТРТУ, 2001. №1 С.61.

31. Вишняков Ю.М., Хашковский В.В. Параллельно-конвейерная обработка документов в сканцентре.—Таганрог, ИСАПР, 2001.

32. Власенко H.A., Краюхина Т.С. Об алгоритме распределения независимых задач по ЦВМ. — Управляющие системы и машины, 1979, № 2, с. 32-34.

33. Власюк Б.А. Задача оптимального расписания при параллельно-последовательном соединении машин. Изв. АН СССР, Техническая кибернетика, 1966, № 4, сс. 67 71.

34. Головкин Б.А. Параллельные вычислительные системы— М.:Наука, Главная редакция физ.-мат. литературы, 1980.—520с.

35. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. — М.:Радио и связь, 1983. — 272 с.

36. Головкин Б.А. Статистические методы формализации и диспетчирования параллельных вычислительных процессов. -Автоматика и Телемеханика, 1974, № 4, с. 163 169.

37. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.—М.:Мир, 1982

38. Джил. Параллельное программирование.—В кн.: Вопросы теории математических машин: Пер. с англ.—М,: Машиностроение, 1964, с. 233-246.

39. Документация к ПО КАВС фирмы ABBYY.

40. Дунин-Барковский И.В., Смирнов H.B. Теория вероятностей и математическая статистика в технике -Гостехиздат, 1955

41. Дэвис Д., Барбер Д. Сети и связи для вычислительных машин, пер. с англ. п/р Цыбакова Б.С. -М:Мир, 1976

42. Евреинов Э.В., Косарев Ю.Г. О возможности построения вычислительных систем высокой производительности.—Новосибирск, изд. СР АН СССР, 1962. 39 с.

43. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности.—Новосибирск, Наука, 1966. 308 с.

44. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы.—Новосибирск, Наука, 1978.

45. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания: Теория и применения к сетям ЭВМ -М:Радио и Связь, 1988

46. Зайцев С.С. Описание и реализация протоколов сетей ЭВМ -М:Наука, 1989

47. Зайцев С.С. Транспортировка данных в сетях ЭВМ -М:Радио и Связь, 1985

48. Зиновьев Э.В., Стрекалов A.A. Сетевые аспекты построения банков данных. // Тез. докл. II Всесоюз. Семинара по вычислительным сетям,—Москва, Рига, 1986. Ч.З. с291-294.

49. Зинченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ-Киев:Техннса, 1986

50. Инст. Киб. им. Глушкова, Локальные и распределенные системы обработки данных, сб. науч. Трудов -Киев, 1984

51. Информационные сети и их анализ //сб. статей, АН СССР, Инт проблем передачи информации -М:Наука, 1978

52. Информационные сети и их структура -М:Наука, 1976

53. Каган Б.М. Электронные вычислительные машины и системы. —М.:Энергоатомиздат, 1985.-592 с.

54. Канцедал С.А. Вычислительные алгоритмы решения задач теории расписаний. — Известия АН СССР. Техническая кибернетика, 1982, №3, с. 42-51.

55. Каспшицкая М.Ф., Сергиенко И.В. К вопросу о планировании процесса решения задач на комплексе ЭВМ.—Кибернетика, 1970, №5. с.41-45.

56. Колесников Д.Г. Оптимизация распределения информационных файлов в сетях ЭВМ с параллельной обработкой.: Дисс. к.т.н. / ДонГТУ., 1999.

57. Константинов В.И., Миренков Н.Н. Функционирование однородной вычислительной системы при наличии приоритетного потока больших задач. В кн.: Вычислительные системы, Новосибирск: ИМ СО АН СССР, 1970, вып. 42, с. 47 58.

58. Корнеев В.А. Введение в теорию сетей связи, Уч.пособие, -Рязань, 1980

59. Корнышев Ю.Н. Теория телетрафика -М:Радио и Связь, 1996

60. Косарев Ю.Г., Миренков Н.Н. Математическое обеспечение однородных вычислительных систем.—Вычислительные системы/ИМ СО АН СССР,— Новосибирск, 1974, вып. 58, с 61-79.

61. Кульба В.В. и др. Резервирование данных в сетях ЭВМ -Казань, 1987

62. Кутепов В.П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения. — Известия РАН. Теория и системы управления, 1996, N 5, с. 97-114.

63. Лорин Г. Распределенные вычислительные системы / пер. с англ. Антропова В.А., Евреинова Э.В. -М.Радио и Связь, 1984

64. Максименков А.В. Анализ алгоритмов диспетчеризации задач мультипроцессорной ЭВМ. — Управляющие системы и машины, 1978, N 3, с. 62-68.

65. Максименков A.B. Распределение задач по машинам сети ЭВМ.— Автоматика и вычислительная техника, 1986, N 2, с. 3-10.

66. Максименков A.B., Селезнев M.JI. Основы проектирования информационно-вычислительных систем и сетей ЭВМ -М:Радио и Связь, 1991

67. Маматов Ю.А. Организация работы мультипроцессорных СЦВМ с многоуровневой памятью //Дис. на соискание ученой степени д-ра. техн. наук.

68. Мафтик С. Механизмы защиты в сетях ЭВМ -М:Мир, 1993

69. Панишев A.B. Эффективные алгоритмы упорядочения работ в системах с параллельно действующими приборами.—Дисс. докт. техн. наук, Харьков: ХАДИ, 1989. 343 с.

70. Пашкеев С.Д. Основы мультипрограммирования для специализированных вычислительных систем.—М.: Сов. Радио, 1972.— 183с.

71. Поспелов Д.А. Введение в теорию вычислительных систем.— М.:Сов.Радио, 1972, 280 с.

72. Построение сетей ЭВМ // М. Като, Д. Иимура. пер. с яп. Малицкого М.Ф., п/р Рощина -М:Мир, 1988

73. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением -М.:Энергоатомиздат, 1983

74. Программное обеспечение неоднородных вычислительных систем: анализ и реализация / Васильев Г.П., Горский В.Е., Шиудкулис В.И., Саух Н.М. -М.:Финансы и Статистика, 1986

75. Протоколы информационно-вычислительных сетей -М:Радио и Связь, 1990

76. Процессы автоматизированной обработки информации: состояние, перспективы, новые технологии, сб. науч. Трудов п/р Велесько -МД990

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

78. Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации -М.Финансы и Статистика, 1998

79. Разумов О.С. Организация данных в вычислительных системах -М.: Статистика, 1978

80. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии.—Журнал вычислительной математики и математической физики, 1973, т. 13, №5, с. 1200-1209.

81. Саак А.Э. Анализ функционирования параллельно-конвейерных систем в условиях неопределенности. Дисс. канд. техн. наук, Таганрог: ТРТИ, 1993. - 323 с.

82. Самофалов К.Г., Луцкий Г.М. Основы теории многоуровневых конвейерных вычислительных систем -М.: Радио и Связь, 1989

83. Седухина Л.А., Хорошевский В.Г. Стохастические алгоритмы функционирования однородных вычислительных систем. — Автоматика и телемеханика, 1973, № 3, с. 121-128.

84. Сетевые протоколы и управление в распределенных вычислительных системах / отв. ред. Лазарев В.Г., АН СССР, Институт проблем передачи информации -М.:Наука, 1986

85. Сети ЭВМ //Глушков В.М., Калинченко Л.А., Лазарев В.Г. -М:Связь, 1977

86. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычислительных систем / п/р Авена О.И. -М.Наука, 1991

87. Системы параллельной обработки, пер. с англ. -М.:Мир,1985

88. Ситникова О.Д. Задача теории расписаний в многостадийной системе с параллельными приборами.—Кибернетика, 1988, №6. с. 114-115.

89. Современные телекоммуникационные технологии и услуги связи в России //труды конференции СТТУ'95 -Мин.Связи РФ, РАН РФ, 1995

90. Сотсков Ю.Н. Использование устойчивости оптимальных расписаний для синтеза информационно-вычислительных сетей.— Автоматика и вычислительная техника, 1990, N 3, с. 12-19.

91. Сотсков Ю.Н. Сетевые модели и методы теории расписаний,—Автореф. дисс. докт. Физ.-мат. наук, Минск: ИТК АН БССР, 1991.-42 с.

92. Сотсков Ю.Н. Устойчивость оптимальных по быстродействию расписаний.—Журнал вычислительной математики и математической Физики, 1989, N5, с. 723-731.

93. Спесивцев A.B. Погрешность некоторых приближенных алгоритмов составления многопроцессорного расписания. — Известия АН СССР. Техническая кибернетика, 1985, № 6, с. 22-28.

94. Стобний A.A., Паныпин Б.Н. Программное обеспечение управления вычислительным процессом в ВЦ и сетях ЭВМ -Киев: Наук. Думка, 1983

95. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. —М.: Наука, 1989. — 328 с.

96. Танаев B.C., Шкурба В.В. Введение в теорию расписаний.— М.:Наука, 1975,—256 с.

97. Тербер К. Дж. Архитектура высокопроизводительных вычислительных систем.—Пер. с англ.—М.:Наука, 1985.

98. Трусов С.С. Об эффективности простых диспетчеров.— Известия АН СССР. Техническая кибернетика, 1973, №4, с. 150-160.

99. Флинт Д. Локальные сети ЭВМ .архитектура, принципы построения, реализация //пер. с англ. Миримова М.Л., Самохвалова Е.Г. -М:Финансы и Статистика, 1986

100. Хащковский В.В. Оптимизация параллельно-конвейерного вычислительного процесса в сканцентре.—М.: Программные продукты и системы, 2002, №1.

101. Хашковский В.В. Организация вычислительного процесса в сканцентре.—Материалы 3-й Всероссийской научной конференции молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения», Таганрог, 2000.

102. Хорошевский В.Г. Алгоритмы Функционирования однородных универсальных вычислительных систем. —Автоматика и вычислительная техника, 1972, № 3, с. 35-41.

103. Хорошевский В.Г. Инженерный анализ функционирования вычислительных машин и систем — М.: Радио и связь, 1987. — 256 с.

104. Чефранов А.Г. Исследование и разработка алгоритмов оперативной загрузки многопроцессорных вычислительных систем со множественными потоками команд и данных. — Дисс. канд. техн. наук, Таганрог: ТРТИ, 1984.

105. Чефранов А.Г. Методы и средства адаптивного управления ресурсами параллельно-конвейерных вычислительных систем: Дисс. д.т.н. /ТРТУ

106. Чефранов А.Г., Саак А.Э. Вероятность соблюдения директивных сроков многопроцессорной системой.—Автоматика и вычислительная техника, 1987, № 6, с. 67-71.

107. Чефранов А.Г., Саак А.Э. Детерминированные и вероятностные оценки эффективности многопроцессорных систем. -Труды 1 Всесоюзной конференции «Проблемы создания суперЭВМ, суперсистем и эффективность их применения», Минск:МРТИ, 1987, ч. 2, с. 196-197

108. Шахбазян К.В., Тушкина Т.А.,Сохранская B.C. Статистические испытания различных методов диспетчеризации для многопроцессорных систем. -Программирование, 1976, № 4, с.91 100.

109. Шахбазян К.В., Тушкина Т.А., Сохранская B.C., Товкач JT.M. Эксперимент по реализации алгоритмов диспетчеризации для многопроцессорных систем. — Управляющие системы и машины, 1975, № 3, с. 84-85.

110. Шварц М. Сети ЭВМ: Анализ и Проектирование, пер. с англ., -М:Радио и Связь, 1981

111. Элементы параллельного программирования. — Под ред. Котова В.Е., М.:Радио и связь, 1983. — 244 с.

112. Янбых Г.Ф., Эттингер Б.Я. Методы анализа и синтеза сетей ЭВМ -Л:Энергия, 1980

113. Яшин С.Ф. Анализ очередей в ЭВМ -М.:Радио и Связь, 1989

114. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimenensions.—SIAM J. Comput., 1980, v. 9, № 4, p. 846-855.

115. Cho Y., Salmi S. Bounds for list schedules on uniform processors. —SIAM J. Comput., 1980, v. 9, № 1, p. 91-103.

116. Coffman E.G., Garey M.R., Johnson D.S. An application of bin-packing to multiprocessor scheduling.—SIAM J. Comput., 1978, v. 7, № 1, p. 117.

117. Coffman E.G., Leung J.Y.-T., Slutz D. On the optimality of fast heuristics for scheduling and storage allocation problems.—Found. Contr. Eng. (PRL), 1978, v 3, № 4, pp. 161-169.

118. Gonzalez Т., Ibarra O.H., Salmi S. Bounds for LPT-schedules of nonidentical uniform processors.—SIAM J. Comput., 1977, v. 6, № 1, p. 155166.

119. Graham R.L. Bound of multiprocessing timing anomalies. SIAM J Appl. Math., 1969, v 17, № 2, p. 416-429

120. Ibarra O.H., Kim C.E. Heuristic algorithms for scheduling independent tasks on nonidentical processors.—J. ACM, 1977, v. 24, №2, p. 280-289.

121. Бурцев B.C. Принципы построения многопроцессорных вычислительных комплексов "ЭЛЬБРУС". Препринт №1. М., ИТМ и ВТ АН СССР, 1977.1261 Гузик В.Ф. Модульные интегрирующие вычислительные структуры. М.:Радио и связь, 1984.

122. Каляев А.В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1982.1 126,127 — Труды ученых ТРТУ, внесших существенный вклад в развитие многопроцессорных вычислительных систем.1. УТВЕРЖДАЮ»

123. Проректор по учебной работе1. АКТоб использовании в учебном процессе результатов кандидатской диссертации В.В. Хашковского «Разработка и исследование методов организации параллельно

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

125. Технологии массового ввода и обработки информации;

126. Архитектуры систем массового ввода;

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

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

129. Зам. декана факультета автоматики и вычислительной техники по научной работе,конвейерных систем массового ввода»к.т.н., доцент1. В.Я. Югай

130. Заведующий кафедрой математического обеспечения и применения ЭВМ д.т.н., профессор1. П.П. Кравченко1. УТВЕРЖДАЮ»

131. Первый проректор— проректор по научной работе

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

133. Расчет годового экономического эффекта прилагается.

134. Проректор по информатике Таганрогского государственного радиотехнического университета Директор Ростовского областного центра новых информационных технологий д.т.н., профессор В.М.Курейчик

135. Проректор экономике Таганрогского государственного радиотехнического университета д.э.н., профессор ^у Н.В.Лазарева1. УTBE РЖДАЮ»

136. Стоимость работ по вводу данных где:5Х—заработная плата обслуживающего персонала и операторов; Б2—амортизационные расходы по эксплуатации средств вычислительной техники (ВТ).

137. Заработная плата обслуживающего персоналаt • п ■ г,где:

138. Ь = 12—время эксплуатации в месяцах; п—число задействованных сотрудников; средняя заработная плата сотрудника.

139. Амортизационные расходы по эксплуатации средств (ВТ)— £ * А. * С /где:t = 12—время эксплуатации в месяцах; А 0.25—амортизационный коэффициент; С—стоимость парка средств ВТ.3. Базовый вариант (база).

140. Время ввода одного бланка при базовом варианте ввода бланков рассчитывается по формуле1м = ^ + + Ьу ,где:

141. Ь5—среднее время сканирования одного бланка на планшетном сканере;

142. Ьк—среднее время распознавания одного бланка;среднее время верификации результатов распознавания для одного бланка;

143. По статистическим данным ЮРЦ СканТех, при реализации базового варианта

144. Тм = (ts = 30) + (tjj = 20) + (tv = 180) = 230 сек. , Производительность 1-го оператора в день рассчитывается поформуле1. К = Кчасов