6CAD-CAE-23 Упорядочение (1014142), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

а) запросы к памяти,

б) время исполнения,

в) стоимость.

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

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

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

COST(ST)=Tx p(S)

где p(S) - многочлен степени d_i ; обычно d=1 (однако, иногда d=0, а в некоторых случаях, когда большие запросы к памяти нежелательны, d=2). Для наших иллюстративных целей вполне достаточно взять p(S)=S.

Если основой сравнения является общее время работы, то следует выбрать алгоритм RCM.

Если наибольшее значение имеют время решения, или суммарное время разложения и решения, или суммарная стоимость разложения и решения, то нужно выбрать алгоритм QMD.

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

QMD дает несколько лучшее упорядочение, чем ND, что отражается в меньших времени и стоимости на этапах разложения и решения и в меньших запросах к памяти.

Однако упорядочение для ND вычисляется значительно быстрее, чем для QMD, что в итоге приводит к меньшим значениям для общей стоимости и общего времени для ND по сравнению с QMD.

У IWD - превосходные характеристики в категориях стоимости и памяти.

Запросы к памяти

1. Для некоторых методов накладная компонента памяти очень значительна, даже для больших задач, где ее относительная важность несколько уменьшается.

Для QMD

Для RCM накладная память

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

Например, при сравнении RCM и QMD исходят только из объема основной памяти, то при всех N следовало бы выбрать QMD.

Между тем, реально потребляемая память у метода RSM меньше, вплоть до N=1500.

Время исполнения

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

Тем самым при возрастании N относительно уменьшаются издержки, связанные с инициированием циклов.

В работе Collins R.J. Bandwidth reduction by automatic remembering // Iut.I Number. Meth. Eng/ - 1973/-Vol.1, No. 6 p.345 представлен метод перенумерации узловых неизвестных, основанный на фронтальном алгоритме СМ. Здесь же представлена таблица наиболее распространенных алгоритмов минимизации ширины ленты системы уравнений МКЭ применительно к 11 примерам, реализованным на ЭВМ IBM 360/85.

1) Катхилл и Макки (СМ).

Cuthill E., Mc.Kee T. Reducing the Bandwidth of Space Symmetric Matrices//ACM, Nat. Conf. - San Francisco, 1969, P157-172.

2) Розен (RR).

Posen R. Matrix Bandwidth Minimization// Prac. Of ACM Nat. Conf. - 1968. - P.585-593.

3) Акьюца и Утку (AU).

4) Грумс (HG).

5) Коллинз (RC).

Характеристики

Список файлов лекций