автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему: Автоматическое сжатие данных в вычислительных системах

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему: Автоматическое сжатие данных в вычислительных системах

Работа выполнена в Московском государственном инженерно-физическом институте (техническом университете).

доктор технических наук, профессор Перминов Олег Николаевич.

доктор технических наук, старший научный сотрудник Кузнецов Сергей Дмитриевич

кандидат технических наук, доцент Кларин Аркадий Павлович

Вычислительный центр РАН

Защита состоится ^Ау 1996 г. в часов && мин. на

заседании диссертационного совета Д053.03.04 в МИФИ по адресу: 115409, Москва, Каширское шоссе, д. 31, МИФИ, тел. 323-91-57, 324-84-98.

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

Автореферат разослан * * 1996 г.

Просим принять участие в работе совета или прислать отзыв в одном

экземпляре, заверенный печатью организации.

Ученый секретарь диссертационного совета доктор технических наук, профессор

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

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

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

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

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

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

Научная новизна работы состоит в том, что впервые;

• предложена классификация существующих схем сжатия данных;

• предложена методика формальной оценки мощности адаптивных схем сжатия;

• предложен критерий оценки применимости схемы сжатия для работы в автоматическом режиме в компоненте ОС и критерий оценки сбалансированности реализации схемы сжатия;

• сформулирована и решена задача выбора оптимальных параметров кодера в словарной схеме сжатия;

• разработана и предложена адаптивная схема сжатия данных без потерь, определена ее мощность и проведено ее сравнение с существующими схемами по мощности;

• предложена эффективная реализация разработанной схемы со временем выполнения одного шага 0(1).

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

• новая методика автоматического сжатия данных без потерь в вычислительных системах

• новые методы формальной и экспериментальной оценки схем сжатия данных

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

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

■ иметь широкий спектр практического применения: от прикладных программ и использования в компоненте ОС .- до размещения в контроллерах внешних устройств, бортовых компьютерах и микропроцессорах. Реализованный на ПЭВМ IBM/PC программный комплекс автоматического сжатия данных на дисковом устройстве, позволяет в среднем удвоить эффективный объем накопителя на магнитном диске, при снижении средней производительности обмена с устройством на 20-30 процентов, позволяя таким образом программным путем увеличить "аппаратные" возможности вычислительного комплекса. Так как в настоящее время вычислительная техника устаревает морально значительно быстрее, чем физически, то использование разработанного комплекса позволяет продлить срок ее службы.

Внедрение. Эффективность разработанных в диссертационной работе методов интеграции автоматического сжатия в'структуру вычислительного комплекса подтверждена положительным опытом их практического использования. При непосредственном участии автора результаты работы были внедрены в вычислительном центре. ЦНИИ "Циклон", в конструкторских бюро электрозавода им. Куйбышева, а также в АОЗТ "Альтер Системы"

Личный оста д. Все основные положения и результаты, выносимые на заидоту, получены автором самостоятельно.

Апробпция работы. Результаты работы докладывались на ежегодной международной конференции Technology of Object-Oriented Languages and Systems'14, Santa-Barbara, CA, 1994 год.

Публикации. Основные результаты, полученные автором, опубликованы в работах [5],[8]. Результаты исследований опубликованы в . работах [1]-[4], [6]-[7]. Ссылки на указанные работы приведены в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Работа содержит 110 стр., в том числе 107 стр. машинописного текста, 24 рисунка, 8 таблиц, а также список

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

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

Термин сжатие данных здесь и далее будет обозначать процедуру их преобразования к более компактной форме, из которой в дальнейшем можно восстановить оригинал или некоторое приближение к нему. Будем называть, алфавитом А некоторое непустое конечное множество. Элементы алфавита будем называть символами. Строкой s над алфавитом А будем называть конечную последовательность символов j„ такую что для любого /', s, принадлежит Л. Определим меру близости строкs и s" над алфавитом А, как функцию М(s, s"), возвращающую 0 в случае, когда строки в точности совпадают, и некоторое число, характеризующее степень их различия, в противном случае. Пусть также F - преобразование строки s над алфавитом л в строку i' над алфавитом С, а F' - преобразование строки s' над алфавитом С а строку s" над алфавитом А. Будем называть схемой сжатия пару <F.F'>, такую что \M(s, f' (F(s))\ <= с, для заданного и >*-- С. Будем называть схемой сжатия без потерь пару <F,F'>, такую что \м(s, F'(F(s>>\ = и. Будем называть схемой сжатия с потерями пару <f,F'>, такую что 0 <\M(s. F'(F(s)J\<= с, для заданного е > 0. Общая схема процесса сжатия приведена на рисунке 1.

Входной |_ поток 1 Модель |_^ Кодер S Выходной поток |

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

Сжатие данных в режиме off-line подразумевает, что модель сообщения полностью построена еще до начала процесса кодирования. При on-line или адаптивном' сжатии модель данных постоянно обновляется по мере

обработки и кодирования очередного фрагмента сообщения. Общая схема адаптивного сжатия приведена на рисунках 2-3. Рисууюх 2. Обиия схема процесса адаптивного сжатия

📎📎📎📎📎📎📎📎📎📎