Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2003


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритм візуалізації графічних сцен для вирішення завдань геометричного моделювання в САПР'

    Текст наукової роботи на тему «Алгоритм візуалізації графічних сцен для вирішення завдань геометричного моделювання в САПР»

    ?ється та з них, при приміщенні елемента в яку спостерігається найменша приріст імовірною завантаженості МКП. Таким чином, будуть забезпечені як метричні, так і топологічні показники якості розміщення, що визначають можливості і якість подальшої трасування.

    681.3

    О.В. Коновалов

    АЛГОРИТМ ВІЗУАЛІЗАЦІЇ ГРАФІЧНИХ СЦЕН ДЛЯ ВИРІШЕННЯ ЗАВДАНЬ ГЕОМЕТРИЧНОГО МОДЕЛЮВАННЯ В САПР *

    . [1], -

    няемое в САПР, використовують складні тривимірні графічні макети або тривимірні сцени [2,3], які, як правило, створюються з метою отримання макси, -чи. Завдання візуалізації тривимірних об'єктів такі, як трасування (Ray Tracing) або зворотна трасування (Ray Casting) променів в рамках сцени, відносяться до NP-. , -,, ряд обмежень. Так, симетричні багатопроцесорні системи, призначені для збільшення продуктивності завдань, що використовують механізм парал-,

    програмне забезпечення накладається ряд обмежень, пов'язаних з поділом доступу до низькошвидкісним ресурсів спільного використання таким, як IDE-інтерфейси, RAM, BUS, і т.д.

    Для візуалізації складних графічних макетів, що складаються з безлічі елементів, паралельні обчислення є найбільш ефективним рішенням, застосовним не тільки для симетричних багатопроцесорних систем, але і для обчислювальних кластерних мереж таких, як Beowulf [10] або Mosix [11-16]. В даний час потенціал систем даного типу практично не використовується, оскільки для обробки завдань в таких умовах необхідні нові методи, якісно відрізняються від існуючих.

    Особливості даної реалізації. Як ос нові для системи розподілених обчислень завдання візуалізації складного тривимірного макета автором була обрана модифікована модель реалізації кластерних рішень Mosix з знову розробленим алгоритмом настройки обчислювального кластера, що дозволило досягти ефективності роботи обладнання, близькій до максимальної при розрахунках складних тривимірних сцен.

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

    Linux. ,

    використані методи прийняття рішень [4], що базуються на нейромережевих і

    * Робота виконана за підтримки Мін. освіти, грант № Е02.2.0-44

    ,

    .

    Під вузлом кластера в даному випадку розуміється один комп'ютер, що надає свої ресурси розподіленої обчислювальної середовищі. Слід зазначити, що хоча кластерним конструкціям моделі Мо81х не властиво наявність центрально,

    побудова обчислювального комплексу. При побудові практичної реалі-

    , , , ,

    зв'язку з дублюванням, коли кожен з вузлів пов'язаний з сусіднім двома каналами: одним прямим і одним комутованих.

    алгоритм.

    1. Початкова оцінка складності візуалізації модулів (СВМ), що містяться в описі сцени (проводиться за кількістю явних елементарних складових:,,,).

    См = Е elm

    де Див- СВМ, а ЕЬм - приблизна оцінка складності візуалізації / '- го елемента.

    2. Груба оцінка всієї сцени: виділяються модулі, ймовірно видимі при остаточному складанні макета (проводиться з урахуванням позиції візуалізації (або камери), джерел світла, оптичних властивостей, параметрів середовища і матеріалів об'єкта).

    3. Процес прийняття рішень: ймовірно видимі модулі (ВВМ) відносяться в різні класи, групуються за оцінками складності, в відповідність п.1 () .2 ( ,

    візуалізації і розташуванням об'єкта всередині сцени) даного алгоритму.

    4. Процес прийняття рішень: ймовірно невидимі модулі (ВНМ) так само ставляться в різні класи, групуються за оцінками складності в

    .1 .

    5. ВВМ, найбільш складні і максимально наближені до точки

    ,

    :

    O = {X Y X Y

    b bound bound bound bound

    X = X Y = Y X = X Y = Y

    bou "dmjn minMF 'boundmjn minMF' boundmax maxMp 'boundmax maxMP'

    MP ,

    , , bound - вказує на те, що дана координата є частиною безлічі областей Ob, а індекси min і max відповідно вказують межі розташування координати на проекційної площини.

    Ця операція проводиться так, щоб побудовані області покрили всі (), -дущую площа візуалізіруемой сцени: операція побудови описують прямокутників проводиться для всіх об'єктів всіх класів, а отримані про, ,

    .

    6. Підраховуються складності візуалізації областей (СВО), виходячи з

    i = 1

    власної площі і сумарною складності об'єктів, захоплених описують межами області. При оцінці враховуються всі модулі, включаючи ВНМ і частково включені.

    7. У відповідність п.6 будується чергу областей візуалізації (ООВ), сформована за зменшенням параметра складності.

    8. Проводиться початковий розподіл навантаження на вузли кластера:

    8.1. Вибирається найбільш потужний і найбільш вільний вузол.

    Вартість обробки області обраним вузлом Нп порівнянна зі швидкістю обробки основним вузлом Н0:

    КрНп (^ еСНп + ^ абНп + ^ еРнп) ~ (^ РНО + ^^ АЛЕ), де КрНп - коефіцієнт, що показує співвідношення продуктивностей Нп Н0 (

    КрНп = РН</ РНП, а продуктивність РНП обчислюється ядром кластера як сума (), Нп -

    ної тестової завдання з урахуванням пересилання даних і файлових операцій);

    {ПересНп _ Час на пересилання підзадачі вузлу Нп;

    гобрабНп _ Час на рішення підзадачі вузлом Нп;

    РчеРНп - розрахунковий час на обробку поточної черги вузлом Нп;

    гобрабН0 - Час на рішення підзадачі вузлом АЛЕ;

    РчеРН0 - розрахунковий час на обробку поточної черги вузлом АЛЕ.

    8.2. , .8.4 , -

    п.8.3.

    8.3. Область поміщається в чергу на обробку вузлом Нп, перехід до п.8.5.

    8.4. Область поміщається в чергу на обробку вузлом АЛЕ.

    8.5. У ООВ є області, нерозподілені по чергах обробки? Їли так, то перехід до п.8.1.

    9. При роботі розрахункових процедур проводиться постійна балансування

    навантаження між вузлами кластера. (Анадогічние п.9.1-П.9.10 процедури

    ).

    9.1. Є завдання в черзі вузла? Якщо немає - перехід до П.9.10.

    9.2. .

    9.3. .

    9.4. ? - .9.8.

    9.5. , ?

    - .9.8.

    9.6.

    обробку однієї з підзадач, що займають обчислювальні ресурси поточного ().

    9.7. ?

    - перехід до п.9.5.

    9.8. .9.3 , ,

    або не звільняться ресурси на одному їх вузлів кластера.

    9.9. ? - .9.7, - .9.1.

    9.10. вузол вільний.

    10.

    остаточного зображення макета у відповідність з їх координатами, .5.

    11. -, - .9.

    . -

    горітма були розроблені програмний обчислювальний комплекс і тестовий

    генератор тривимірних модулів псевдослучайной форми для наповнення тестових сцен. Полігональна складність візуалізуються модулів (від 4 до 1000 полігонів на об'єкт) вибиралася випадковим чином, як і їх місце розташування в тривимірному просторі сцени. Отримані дані показують, що ідеалізовано, , -

    ватяними для реальних завдань: апріорі можна стверджувати, що загальна виробляй-

    ність обчислювальної системи повинна прагнути максимально, тобто 300% (), .

    Якщо в ідеалізованих умовах, коли всі об'єкти сцени рівномірно розподілені в прямокутній сітці, що накладається на проекційну площину

    , , -ність: для одного вузла 100% з 100% можливих, для двох вузлів 189% з 200% можливих, для трьох вузлів 293% з 300% можливих, то на реальних сценах продуктивності будуть варіюватися в залежності від параметрів наповнення сцени, що показано в таблиці 1.

    1

    Складність СЦЕНИ ПРОДУКТИВНІСТЬ

    1 вузол 2 вузла 3 вузла

    від 50000 до 500000 модулів 100% 127% 148%

    Від 5000 до 50000 модулів 100% 152% 193%

    До 5000 модулів 100% 154% 196%

    . -

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. ІМ. Норенков. Основи автоматизованого проектування: Учеб. для вузів. М .: Изд-во МГТУ ім. Н.е. Баумана, 2000..

    2. О.В. Коновалов. Проблеми формування тривимірних векторних структур. Известия ТРТУ №2, тематичний випуск «Інтелектуальні САПР» Матеріали Всеросійської науково-технічної конференції за участю зарубіжних представників «Інтелектуальні САПР-97». Таганрог: ТРТУ, 1998..

    3. ... . « -

    си доповідей РіЕвНХ ». М .: МЕІ, 1998..

    4. . . .

    градиентного правила. Праці конференцій IEEE AIS'02 CAD-2002. М .: Физматлит, 2002.

    5. Обчислювальні комплекси, системи та мережі / А.М.Ларіонов, С.А.Майоров,

    . . :. .:. . , 1987.

    6.. . :. . .: -. 1990. 320 .

    7.:. ./. . . .:, 1985.

    8. ... .:, 1980.

    9.. . .:, 1981.

    10. /. . , С.Я. Виленкин, І.Л.Медведев. М .: Знергоатоміздат, 1983.

    11. A.Barak, O.La'adan, A.Shiloh. Scalable Cluster Computing with MOSIX for LINUX. The Hebrew University of Jerusalem, 1998..

    12. A.Barak, O.La'adan. The MOSIX Multicomputer Operating System for High Performance Cluster Computing. Journal of Future Generation Computer System, 13, 1998..

    13. A.Barak, S.Guday, R.G.Wheeler. The MOSIX Distributed Operating System, Load Balancing for UNIX. In Lecture Notes in Computer Science, Springer-Verlag, 1993.

    14. A.Barak and A.Braverman. Memory Ushering in Scalable Computing Cluster. Journal of Microprocessors and Microsystems, 22, 1998..

    15. A.Barak, A.Braverman, I.Gilderman and O.Laden. Performance of PVM with the MOSIX Preemptive Process Migration. In Proc. Seventh Israeli Conf. on Computer Systems and Software Engineering, 1996..

    16. Y.Amir, B.Averbuch, A.Barak, R.S. Borgstrom and A.Keren. An Opportunity Cost Approach for JobAssignment and Reassignment in a Scalable Computing Cluster. In PDCS '98, 1998..

    17. . . , . . , . . , . . . -

    вим циклом продукції. М .: Анахарсіс, 2002.

    681.3: 536.2.072

    ..

    Нечіткі ПЛАНУВАННЯ НВІС НА ОСНОВІ еволюційний

    АДАПТАЦІЇ *

    Планування це рання фаза проектування чіпа. Воно дає інформацію про,, -ках. У багатьох додатках, хоча і потрібна хороша топологічна структура, але не вся інформація про всіх модулях є в наявності, або, що ще гірше, частина цієї інформації не точна. Приклади таких додатків - це проектування , -, .

    - , -

    * Робота виконана за підтримки Мін. освіти, грант № Т02-02.3-491


    Завантажити оригінал статті:

    Завантажити