Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Основы теории алгоритмов учеб. пособие

.pdf

Скачиваний:

Добавлен:

19.10.2023

Размер:

6.6 Mб

Скачать

☆

<<< < Предыдущая 1 2 34 / 174 5 6 7 8 9 10 11 12 13 14 15 16 17 > Следующая >>>

			- 30		-
Данную методику перехода^ от сланных матриц к простым
можно применить в алгоритме £>				-	, содержащего разветвления.
При этом элементы			&j't	матрицы С .		составляются для
алгоритмов, находящихся на ветви о "Ь						а значения		->
для алгоритмов,	не входящих в ветвь о rkmatt.
Таким образом, множество наборов						H ji	может быть опи
сано некоторой	£ -системой:				матриц однозначных параметров
. Выбирая из какого набора но одному алгоритму,								мож
но получить множество		\|			решений алгоритма			& .
Задачу выбора наилучшего варианта набора алгоритмов,
составляющих алгоритм		D	, можно упростить,				если перед опти

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


варительные операция над матрицами параметров.
Обозначим через 0			некоторую операцию над компонента
ми матрицы	.	Тогда при определении		для некоторого
-варианта		над выбраннымииз каждой колонки по одной
компоненте	# j l	матрицы	)Cj> проводится операция в		,

|Ц

Например, для Х ? жЯ и	Й1=	4 имеем, что О	представля
ет собой операцию сложения, т .е .
	т
*	jEj	X j i .

r l

Приведем некоторые способы упрощения матриц параметров

алгоритмов.
I .	Если кошюяенты некоторого набора колонки E j
ны между собой	то	можно вывести за мат
рицу. Например,	6 »	Шщ
	6 »	Шщ
	) C u JCw	К+х

К »

ЪС-а К и

(1.26)

ЭСш.4

					- 31	-
где число вариантов				S *	Г Т ^	=	3 4 2	3 = 72.
	Пуоть компоненты голонкя					Е* X u * )С а * Х « в X i
а Е*.	1Счш Х и .ш Хи				. Тогда		Eg	Е<
				К.	Б*		Kai	Х*<
				К.	Б*		л »	X u
			X f -	K .Q * t 8			л »	X u
			X f -	K .Q * t 8			х «	X u
							х «	X u
							ХгЧ	(1*27)
							ХгЧ
	Запись		(1 .27)епдержитыеныпее число вариантов, т.в.
S =	1 - Г 4 - 3		= 12.
	2 .	Бели набор			состоит		только из одной компоненты
X u ,	то	ее можно вынести за матрицу.
	3 .	Если компоненты X jl				матрицы Хр есть множества и

если меняются элемент, которые принадлежат каждому множеот-,

ву	Xji , то такие элементы можно вынести за матрицу без				обо
значения принадлежностей к колонкам,					;
	Например, в выражения		Eg	_
	Et		Eg	Cg
	( 1 . к> М	{ к» k g }		f k « k , k , j
	( к . к , 1	{ к* kg k i }		( к . к . )
	I U	( к» кi J		{ к . k . i
	( к , 1. 1			1 к . J
за	матрицу можно вынести	kg	, так как любой вариант,		со

ставленный из трех компонент (из каждой колонки беретоя од на компонента), оодержит после операции^единенйяко1^ н е в ^ -

множеотво с элементом	kg . Тогда
1 k* kj t	1 K.I	1 к * Ы
K “ (ka} U	l k , k , l	( Ы
K “ (ka} U	( Ы	( k i j
0	( Ы	( k i j
( M		Ф
		Ф

						32
где		-	пустое тожество.
	Данный прием является частным случаем более общего:
если компоненты множества некоторой								\| -ой колонки содержат
одинаковые элементы, то их можно вынести за матрицу (напри
мер.;	k s	) .	Тогда
				(	к .		) Ф		{	кл]
					Ф		(	Ы	Ф
К	'	\|	Щ	и	Ф		Ф		(	Ы
К	'	\|	Щ	и
					(	к,1				Ф
что позволяет				сократить количество операций соединений.
	4.			К двум и более			алгоритмам,			описанным системами п
тых матриц, применима операция соединения, а над соответству
ющими параметрами проводится операция Q ,									если алгоритмы не
зависимы (независимыми считаем те алгоритмы, которые имеют
один вход и один выход).
I	Пуоть					где	b i *	В и*-	независимые алго
ритмы и B i* {Ei.Ea, Е * ] ,					а	Ьа.*{ Еа, Е »,			3		я
			E ,s ‘ *»						SaEjE*
				»		X f а * -

Тогда b i l / f t . “ { Е м Е и . Е и . Е ^ }

Ei Еа Ев Вt(

^*fM ~ I	0	# \|* j 4 I-
Рассмотрим обобщенный случай
	( €• « i i	• • ' ? £ * , )

~ 33 -

( B i - U j l ) .

Каждый элемент В^М описан системой простых матриц

Ejftt

# a t p 35 I

1 .

Если независимые алгоритмы охвачены циклом, то алго- . ритм М является сложным и множество его решений описывается сложной системой « Для преобразования сложных систем матриц в простые, Как уже отмечалооь, необходимо умно--

жить сложную матрицу на матрицу-строку L	, содержащую
постоянные коэффициенты.

5.При умножении матрица на постоянный коэффициентC

или на ( * * f £-6а Д»и)каждая компонента матрицы умножа ется на этот коэффициент.

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

Ei т ) ,

* ги - \| * мИ	),
( f - i ,*»••••% )■
которые описывают множество решений алгоритма	М ‘	.
1 .2 . Обобщенный критерий
Представляя эффактнвнесть вычислительных алгоритмов
перечислением их параметров в виде кортежей и матриц,		прихо
дим к чаотным показателям алгоритмов, с одной стороны,		и

структур УВС - с другой.

На основании частных показателей монно сформулировать критерий [46, 47, 48, 49] , характеризующий степень согла сования структур алгоритмов со структурами УВС. Прежде чем сформулировать этот критерий, рассмотрим более подробно част ные критерии.

- 34 -

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

ность параметров	алгоритма А в виде множеств
X	- { Х , , - - - » Х « ] . ( i “ M , •••> £)'

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

->X lV i),


где \}L - чиоло компонент параметра			;
6 - число параметров алгоритма		А	.
Если X i характеризует состав		операций в алгоритме, то
V i)	определяет количество операций			1.-го

. типа. В зависимости от конкретных требований одни параметры играют первостепенную роль, а другие оказываются несуществен ными. В таком случае можно выбрать такое подмножество X ' , которое в достаточной мере характеризует структуру алгоритма А ( Х ' с Х ) . Тогда указанный выше критерий первого типа мо жет быть определен в виде функции, представляющей собой неко-v торую зависимость от параметров, входящих в множество X * • т . е . в виде

F ( A ) - F [ а ( х * ) ] .

Обычно выбирают критерий Р(А )так, чтобы качество ал горитма, представляемое множеством УС' его параметров, оце нивалось по экстремальному значению кмтерия при известных ограничениях на некоторые параметры X j 6 X * .

Второй тип критериев имеёт особенность, что они пред-

- 35 -

назначаются для оценки вычислительных устройств вне зависи-

I мости от ввда обрабатываемой информации. Такие критерии могуч : быть полезными при сравнении различных вариантов структур вн^

числительных устройств,		близких по назначению. По аналогии		!
с предыдущим обозначением совокупность параметров УВС в виде
множества Y *	Y<f .	YkI	Такими параметрами могут быть	I
быстродействие,	разрядность,		объем намятой' различных типов,	j

: система команд и др. Некоторые параметры могут оказаться мно-j-

покомпонентными, т .е . в				общем случав можно записать
Г			Y j - ( *	*	* ’ yi - Pi ) »
где	JMj	-	число компонент вектора			Yjj	5
	J<	-	число параметров		структуры машины М .
Если	у		характеризует память машины, то
определяет			объем памяти		-го	типа в	общей структуре ма-

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

F ( m ) - f [ m ( y ')1,

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

ва	Y
	В общем олучае обобщенный критерий соответствия струк
тур алгоритмов		структурам УВС может быть представлен в виде
	F ( A , M )* - некоторой зависимости между параметрами
алгоритма		и структуры У . Если Д о - множеотво воз-

х )- такая зависимость была предложена к .т .н . ПОПОВЬЙ В«А»

- 36 -

можных модификаций алгоритма решаемой задачи & , а М© - множество возможных вариантов структур, способных реализовать множество алгоритмов Ао , то,как и в предыдущих случаях, выбор оптимального соответствия алгоритма и машины будет оп

ределяться экстремальными значениями критерия				F ( А ,	И )	,
В	конкретных условиях множества	А« и	Me	ограничиваются
определенными требованиями по некоторым параметрам из					X	и
	У ' . Поэтому оптимальное соответствие будет разыскиваться
в	подмножествах Ао ( д ; с А .)	и M i	( M i с м . )

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

дится к нахождению такой пары Aopt и И oft	, которые свои
ми параметрами образуют критерий F (А, М), в	максимум или ми

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

количестве пар вида(Ао£., Hoj), где 1= 1 , 2 , . , . Н			; j =
1 , 2 , . , . ,	HI	; Н и ГП - соответственно мощности множеств
Ао	и	Мо .

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

рия эффективности F ( А ,М).

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

. и видом алгоритма, подлежащих реализации в машине. Логичео-

- 37 -

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

1. Число адресов в командах машины.

2 . Наличие или отсутствие совмещения выбора команды из памяти и выполнения арифметичеокой или какой-либо другой операции.

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

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

5. Особенность системы команд.

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

записать в виде

ор

(1.28)

где cL , $ , $ - содержание ячеек памяти или регистров арифметического устройства.

Если в операции JL—►2Г символы еС и if означают содержание ячеек памяти, то такая операция выполняется в ма- ' шине пооредотвом передачи информации ^ерез региотр арифмети ческого устройства и имеет вид

Пусть алгоритм, подлекащий реализации УВЫ, оодержит |

- 38 -

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


	F - S i * l + 4 . * * + " "			+ 4 » * " ' >	(1.29)
где	t \|i - число	обращений к памяти в конкретной структуре,
приходящихся на одну			{, -ю операцию вида		(1 .2 8 );
	50с -чи сло	операций		t -го типа (	1 = 1 , 2 , . . . , Ю ).
Нетрудно заметить,		что	записанная функция связывает показате

ли алгоритма и структуры машины, причем

	F ( А , м" ) =		х Y ,
где X Y	-	окалярное произведение двух			ГП -мерных век
торов .
При этом		t - k - 1 ,	"H I .	Оптимальное соответст
вие алгоритма и структуры будет в			случае	F * Fmin
Найдем предельное значение критерия					F ( A , M ) при

фиксированной структуре УВМ и произвольном алгоритме в с то л е качественного и количественного состава оглраций в нем. Запи шем это обстоятельство в виде следующих ограничений:

	M l +	X J + • • •	+	XJm * N	,
				> 0,	( х . з о )
	(y jeC O flii,			ljjt«rCo n s b ,
где	целые положительные числа.
Заметим,	что	*jji = О	в	том олучае,	если некоторая операция

не требует обращений к обычной памяти; в этой операции используютоя "быстрые ячейки", т .е . буферные регистры арифметичес кого устройства. Таким образом, задача нахождения предельных значений потерь времени на обращение к памяти сводится к за даче линейного программирования, в которой линейной формой > являетоя критерий (1 .29), а систему ограничений представляют выражения (1 .30). Для решения этой задачи можно применить,

- 39 -

например, оимплеко-метод и найти предельные значения критерия F(A,M) . После соответствующих выкладок получаем

( т

У д N * F ( А , И У ( т а к f r ) N

( I .3 I)

Бели задан некоторый клаоо адреоных структур в виде

множества

{ M l

с мощностью

то

можно определить

предельные значения критерия

F (А, И)

и в этом олучае,

Пуоть 4 i h

-значение

t -ой компоненты вектора

К -ой структуре (

1 . 2 , . . . ,

)•

При этом имеем

оледущее соотношение

m e n у th ^ 4 i.b ^ m a x

где макоимум (минимум) берется по всем

. Тогда вы

ражение

(1 .31) перепишем в воде

( m i n U i O N * F ( A . M ) < ( m a * y y , ) N .

(1.32)

Для более удобного использования критерия

F C A . M )

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

j t

, для чего в

выражении

>Ci+ * ** + ЪСт ■» М

разделим

обе чаоти

равенотва

на

и получим

f x i - i ,

0 * * i * i .

где

в п

содержание операций

С-го типа в

- относительное

заданном алгоритме. Величину

# 1

можно представить как

час

тоту появления операции

-го типа или в

предельном случае

как вероятность

появления

-ой операции.

Для УВМ интерес представляет использование критерия

F ( A , M ) для целого класса алгоритмов

реализуеьшх на машине. Обозначим вероятность появления

j -ой

задачи

через

. При этом очевидно,

что

‘ v

1 - .

i*1

<<< < Предыдущая 1 2 34 / 174 5 6 7 8 9 10 11 12 13 14 15 16 17 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ