Процессы управления и устойчивость

Рис. 1. Конвейер OpenGL

Упрощенная схема конвейера вычислений стандарта OpenGL 2.0

приведена на рис. 1 [10].

3. Процесс фильтрации. Алгоритм фильтрации изображений

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

четырехугольник из вершин. С ним ассоциируется текстура, генери-

руемая из файла, содержащего исходное фильтруемое изображение.

Область вывода настраивается так, чтобы она полностью заполня-

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

дого пикселя в случае использования фрагментного шейдера опре-

деляется его выходным значением, в противном случае — цветом со-

ответствующего элемента текстуры. В целях устранения возможных

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

На этапе отрисовки данные о текущем обрабатываемом примити-

ве (его вершинах) проходят через вершинный шейдер без изменения.

Информация о текстурной единице, назначенной текущему прими-

тиву, передается далее в фрагментный шейдер, где и производится

непосредственная фильтрация. После процесса растеризации и опре-

деления фрагментов для текущего примитива фрагментный шейдер

вызывается для каждого фрагмента, производит требуемые вычис-

ления, основываясь на цветовых данных текстуры и логике фильтра,

и на выходе выдает новое значение цвета фрагмента. Это значение

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

На уровне приложения объекты шейдерных программ создаются,

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

320

ной программы. Возможно одновременное использование несколь-

ких фильтрующих шейдеров. Следует также отметить, что в фраг-

ментный шейдер можно передавать параметры, реализуя таким об-

разом настройку фильтра.

В связи с особенностями вычислительного конвейера OpenGL, ко-

торый работает с 2D текстурными картами, имеющими квадратные

размеры степеней двойки [11], для тестирования механизма филь-

трации использовались изображения с размерами 64×64, 128×128 и

256×256 пикселей.

4. Пример фильтрации: фильтр Sobel. Оцифрованное изоб-

ражение в памяти вычислительных машин представляет собой дис-

кретный сигнал. Поскольку сигнал — это функция, то в случае изоб-

ражения его можно представить в виде функции цвета пиксела (точ-

ки) от координаты данной точки [4].

Фильтр Sobel фактически осуществляет вычисление двухмерно-

го пространственного градиента от изображения-сигнала, предвари-

тельно преобразованного из цветного к оттенкам серого. Вектор гра-

диента в этом случае характеризует изменение контраста в окрест-

ности текущей точки (пикселя) изображения. В Sobel используется

две операции свертки дискретного сигнала с ядрами в виде матриц

размерности 3×3, одна из которых применяется для определения

градиента в направлении оси X (вдоль строк), другая – для опреде-

ления градиента в направлении оси Y (вдоль столбцов) [5].

При рассмотрении операции свертки предполагается, что зна-

чение сигнала зависит от одной координаты точки, т.е. все точки

изображения как массив значений их цветов v[x, y] представляются

в виде одномерного массива v[x · height + y], где height — ширина

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

u[n] =

N

k=1

v[n − k]h[k],

где h[k] – конечное ядро свертки (kernel), u[n] – результирующий

сигнал.

Ядра свертки обычно имеют размеры, много меньшие по срав-

нению с размерами фильтруемого изображения, поэтому процесс

свертки плавно движется вдоль изображения, в каждой целевой точ-

ке манипулируя квадратом из пикселей. Эти ядра имеют следующий

матричный вид:

321

h

x

=





−1 0 1

−2 0 2

−1 0 1



 ,

h

y

=





−1 −2 −1

0

0

0

1

2

1



 .

Вектор градиента определяется как

g =

g

x

g

y

,

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

g = |g| =

g

2

x

+ g

2

y

,

где

g

x

=

1

k=−1

1

l=−1

v[x + l, y + k] · h

x

[l + 1, k + 1],

g

y

=

1

k=−1

1

l=−1

v[x + l, y + k] · h

y

[l + 1, k + 1].

Далее вводится предельный параметр θ. Производится сравнение

величины вектора градиента с θ, и по полученному результату те-

кущей точке (пикселю) изображения присваивается черный цвет (в

случае g > θ) или белый цвет (в случае g < θ). Результирующее

изображение представляет собой выделенные контуры элементов на

белом фоне. Чувствительность фильтра, а также его чистота в смыс-

ле отсутствия "шумов" (побочных фрагментов, выделенных черным

цветом) зависят от предельного параметра [5].

5. Реализация метода и оценка быстродействия. Разрабо-

танное тестовое приложение поддерживает возможность фильтра-

ции как статических растровых изображений (BMP), так и видеоря-

да (AVI). Для оценки быстродействия метода алгоритм фильтрации

имеет реализации для запуска и на CPU (software-метод), и на GPU

(hardware-метод).

Результаты тестирования позволили дать положительный ответ

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

ражений можно производить с использованием ресурсов графиче-

ского адаптера. Однако, эта возможность, так же как и быстродей-

ствие метода, зависит от типа используемой видеокарты. Для запус-

ка hardware-фильтрации необходим видеоадаптер, поддерживающий

следующие расширения OpenGL:

322

GL_ARB_multitexture, GL_ARB_shader_objects,

GL_ARB_vertex_shader, GL_ARB_f ragment_shades,

GL_ARB_shading_language_100.

Этим требованиям соответствуют видеокарты 5, 6 и 7 поколений

(начиная с RADEON

R

9500 от ATI Technologies или GeForce

R

FX

5200 от NVIDIA Corporation). Разработанная программа тестирова-

лась на нескольких тестовых платформах (таблица 2). В таблице 1

приведены данные о быстродействии фильтра Sobel в случае исполь-

зования исходного изображения с размерами 256 × 256 точек

Таблица 1. Время просчета фильтра

Тестовая платформа

Hardware-метод

Software-метод

I

0.16—0.17 мс

135—165 мс

II

0.38—0.41 мс

146—162 мс

III

0.12—0.13 мс

136—140 мс

Таблица 2. Конфигурация тестовых платформ

Номер

Конфигурация

I

AMD Athlon 2400+, 1Gb RAM, ATI RADEON 9500

II

AMD Athlon 2600+, 1Gb RAM, NVIDIA FX 5200

III

AMD Athlon64 3200+, 1Gb RAM, NVIDIA 6800GS

Из результатов тестирования видно, что hardware-метод значи-

тельно более эффективен в плане быстродействия. Стоит отметить,

что производительность фильтрации незначительно снижается при

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

очередного кадра в видеопотоке и генерацию текстуры. Тем не менее,

результаты дают основание полагать, что hardware-метод теоретиче-

ски позволяет осуществлять фильтрацию потокового видео “налету”,

без задержек.

6. Заключение. Проблема оптимизации и ускорения обработки

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

науки и техники, где скорость и распараллеленность данного про-

цесса особенно важны. Решением задачи фильтрации изображений

средствами графических ускорителей занимаются технические отде-

лы компаний – мировых лидеров в производстве видеоадаптеров –

ATI Technologies Inc. и NVIDIA Corporation [6].

Задача данной работы состояла в демонстрации возможности пе-

ренесения основной вычислительной нагрузки при фильтрации изоб-

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

323

На данный момент активно развивается идея переноса и вычислений

общего назначения на GPU (GPGPU – General Purpose computations

on GPU). Достижения в этом направлении свидетельствуют о том,

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

успешно, а главное эффективно, решаться с применением современ-

ных графических ускорителей.

Литература

1. Баяновский Ю.М., Игнатенко А.В., Фролов А.И. Графическая

библиотека OpenGL. М.: МГУ, 2003. 130 с.

2. Введение в GLSL. http://www.gamedev.ru/articles

3. Краснов М. OpenGL в проектах Delphi.

http://www.soobcha.ru/rushelp

4. Лукин А. Введение в цифровую обработку сигналов (математи-

ческие основы). M.: Лаборатория компьютерной графики и муль-

тимедиа МГУ, 2002. 44 c.

5. Matthews J. An Introduction to Edge Detection: The Sobel Edge

Detector. http://www.generation5.org/articles.asp.

6. Mitchell J.L. Image Processing with 1.4 Pixel Shaders in Direct3D,

3D Application research Group, ATI Research.

7. Kessenich J., Baldwin B., Rost R. The OpenGL Shading Language.

3DLabs Inc., 2004.

8. Kessenich J. Features of the OpenGL shading Language. 3DLabs Inc.,

2004.

9. Kilgariff E., Fernando R. The GeForce 6 Series GPU Architecture.

GPU Gems 2. NVIDIA Corporation, 2005.

10. OpenGL pixel and vertex shaders. http://www.gamedev.ru/articles.

11. OpenGL programming guide. Addison-Wasley Publishing Company,

1997.

324

Дмитриев М. Д.

Санкт-Петербургский государственный университет

Оптимальная декомпозиция таблиц

в реляционной базе данных

Рекомендовано к публикации профессором Горьковым В.Ф.

1. Введение. Большинство современных баз данных иcпользу-

ют реляционную модель. Реляционная модель рассматривает три ас-

пекта даннных: структура, целостность и обработка данных. При

проектировании и модификации базы данных возникает задача оп-

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

ляционные таблицы. Оптимальность разбиения рассматривается с

точки зрения трех перечисленных аспектов данных.

2. Постановка задачи. Дадим несколько определений, необхо-

димых для построения математической модели [2].

Определение 1. Отношением или реляционной таблицей R,

определенном на множестве из n типов или доменов T

i

, i = 1, n, бу-

дем называть объект R = {Z, T }, где Z – заголовок таблицы, опре-

деляемый как множество атрибутов вида Z = {(A

i

, T

i

)}, i = 1, n,

A

i

= A

j

, i = j, i = 1, n, j = 1, n, где A

i

– имена атрибутов или имена

столбцов. T называется телом и определяется как множество вида

T = {t

j

}, где t

j

= {(A

i

, ν

ji

)}, i = 1, n, j = 1, m, ν

ji

∈ T

i

, t

j

– кортеж

или строка, ν

ji

– значение атрибута A

i

. Причем в R не существует

t

k

, где k ∈ {1, . . . , m}, для которого существует t

l

, такого, что t

k

= t

l

,

где l ∈ {1, . . . , m}, l = k.

Определение 2.

Потенциальным ключом отношения R =

{Z, T } будет называться K ⊂ Z такое, что: 1) не существует t

l

, t

k

∈ T ,

где l = k, таких, что ν

il

= ν

ik

для любого i : (A

i

, T

i

) ∈ K и 2) для

любого K1 ⊂ K такого, что существуют t

l

, t

k

∈ T , где l = k, такие,

что ν

il

= ν

ik

для всех i таких, что (A

i

, T

i

) ∈ K1.

Замечание 1. Так как по определению 1 все кортежи в отноше-

нии R различны, у отношении R всегда будет существовать хотя бы

один потенциальный ключ.

Определение 3. Зафиксируем один из потенциальных ключей

отношения R, обозначим его P и будем называть первичным ключом

отношения R.

325

Определение 4.

Внешним ключом E в отношении R

2

=

{Z

2

, T

2

} будем называть подмножество E ⊂ Z

2

множества атрибутов

R

2

такое, что ∃ отношение R

1

(R

1

и R

2

не обязательно различны) с

потенциальным ключом P , и каждое значение E в текущем значении

R

2

всегда совпадает со значением P некоторого кортежа в текущем

значении R

1

.

Замечание 2. Вместе с понятием внешнего ключа появляется

понятие ссылочной целостности [2]. База данных не должна содер-

жать несогласованных значений внешних ключей, т.е. для каждого

внешнего ключа существует соответствующий потенциальный ключ.

Определение 5. Пусть определено отношение R = {Z, T }, a

X и Y – произвольные подмножества Z. Тогда Y функкционально

зависимо от X, обозначается X → Y , если при ν

lX

= ν

kX

верно и

ν

lY

= ν

kY

.

Определение 6. Тривиальной зависимостью называется зави-

симость, которая не может не выполняться.

Определение 7. Множесто функциональых зависимостей (ФЗ)

S называется неприводимым, если выполняются следующие усло-

вия: 1) правая (зависимая) часть каждой ФЗ из S является одноэле-

ментным множеством; 2) левая часть каждой ФЗ из множества S

является неприводимой, т.е. ни один атрибут из левой части ФЗ не

может быть опущен без изменения замыкания S; 3) ни одна ФЗ из

множества S не может быть удалена без изменения его замыкания.

Определение 8. Суперключом отношения R назовем подмно-

жество атрибутов отношения R, которое в виде подмножества (не

обязательно собственного подмножества) содержит, по крайней ме-

ре, один потенциальный ключ.

Определение 9. Реляционная таблица находится в первой нор-

мальной форме (1НФ) тогда и только тогда, когда в любом допу-

стимом значении этой таблицы каждый её кортеж содержит только

одно значение для каждого из атрибутов.

Определение 10. Реляционная таблица находится во второй

нормальной форме (2НФ) тогда и только тогда, когда она находит-

ся в 1НФ, и каждый неключевой атрибут неприводимо зависим от

первичного ключа.

Определение 11. Реляционная таблица находится в третьей

нормальной форме (3НФ) тогда и только тогда, когда она находится

во 2НФ, и все неключевые атрибуты взаимно независимы.

Определение 12. Реляционная таблица находится в четвёртой

326

нормальной форме (4НФ) тогда и только тогда, когда она находится

в 3НФ и ∀ ФЗ A → B в этой таблице является тривиальной, или A

является суперключом таблицы.

Определение 13. Реляционная таблица находится в пятой нор-

мальной форме (5НФ), когда она не может разбиваться на более

мелкие таблицы.

Существуют и другие определения нормальных форм. Приведен-

ные здесь определения нормальных форм являются основными.

Задача состоит в нормализации реляционной таблицы данных.

Она заключается в декомпозиции исходной таблицы на более мелкие,

удовлетворяющие определенным условиям, соответствующим опре-

делениям нормальных форм. Процесс разбиения должен быть обра-

тим, т.е. по таблицам, полученным в результате нормализации, мож-

но восстановить исходную таблицу. Это правило целостности базы

данных достигается благодаря наличию первичных и внешних клю-

чей в каждой таблице.

3. Решение. Пусть имеется реляционная таблица R = {Z, T } с

первичным ключом K ⊂ Z и известным множеством ФЗ S = {{A} →

{B}}. Заметим, что приведение таблицы R к 1НФ достигается разби-

ением множества атрибутов исходной таблицы на атрибуты, каждый

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

Это действие элементарное, так что предполагаем, что исходная таб-

лица R находится в первой нормальной форме.

Зададим граф G = (X, F ), в котором X = Z \ K состоит из атри-

бутов таблицы R, не входящих в первичный ключ. Отображение F ,

задающее отношение смежности в графе G, будет отражать степень

нормализации таблицы. Две вершины x

i

, x

j

∈ X в графе G смежны

тогда и только тогда, когда: 1) левая часть ∀ ФЗ из множества S, в

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

x

i

и x

j

, различна и является подмножеством атрибутов первичного

ключа K, т.е. атрибуты, не входящие в первичный ключ, неприво-

димо зависят от первичного ключа; 2) атрибуты таблицы, соответ-

ствующие x

i

и x

j

, входят, соответственно, в левую и правую части

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

взаимно независимы; 3) для атрибутов таблицы, соответствующих

x

i

и x

j

, ∃ ФЗ A → B из множества S, в которую входят оба атрибу-

та таблицы, соответствующие x

i

и x

j

, ФЗ не является тривиальной

и A не является суперключом таблицы.

327

Построим раскраску графа G = (X, F ) π

l

(G) = {C

1

, . . . , C

l

}. В

один класс C

i

раскраски π входят только те элементы множества X,

которые попарно не смежны между собой. Приведем раскраску к ми-

нимальной [1]. Получим χ(G) классов минимальной раскраски графа

G, каждый класс которого определяет таблицу R

k

, k = 1, . . . , χ(G),

такую, что R

k

= {Z

k

, T

k

}, где Z

k

= Z

k

1

∪ Z

k

2

. Z

k

1

состоит из объеди-

нения множества атрибутов R, входящих в первичный ключ, явля-

ющихся общей левой частью для всех ФЗ, в правой части которых

находятся атрибуты, не входящие в первичный ключ таблицы R. Z

k

1

является первичным ключом в таблице R

k

, а также внешним ключом

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

цы R. Z

k

2

состоит из объединения множества атрибутов R, не входя-

щих в первичный ключ, у которых левая часть ФЗ из множества S, в

которую они входят, одинакова и является множеством Z

k

1

, а также:

1) неприводимо зависит от атрибутов множества Z

k

1

, являющегося

первичным ключом таблицы R

k

; 2) атрибуты Z

k

2

взаимно незави-

симы; 3) ∀ФЗ A → B, где A, B ∈ Z

k

, является тривиальной или A

является суперключом таблицы. Таким образом, получено разбиение

исходной таблицы на минимальное количество таблиц, отвечающих

требованиям определения четвертой нормальной формы.

Замечание 3. Меняя условия на смежность в графе G = (X, F ),

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

ни. Т.е., если F задается условием 1), то полученные в результате

разбиения таблицы будут находиться во 2НФ; если выполнены усло-

вия 1) и 2), то полученные в результате разбиения таблицы будут

находиться в 3НФ; если выполнены условия 1), 2) и 3), то получен-

ные в результате разбиения таблицы будут находиться в 4НФ.

4. Пример решения задачи. Рассмотрим задачу нормали-

зации до второй и третьей нормальных форм на примере. Пусть

есть таблица R = {Z, T }, находящаяся в первой нормальной фор-

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: