1.3.2 Опис операційної системи

Програма працює на операційній системі Microsoft Windows версій XP\Vista\7. Windows  сімейство пропрієтарних операційних систем корпорації Microsoft, орієнтованих на застосування графічного інтерфейсу при керуванні. Спочатку були лише графічними компонентами для MS-DOS.

В даний час під управлінням операційних систем сімейства Windows, за даними ресурсу Net Marketshare (Net Applications) станом на грудень 2011 року, працює близько 86% персональних комп'ютерів [7].

Операційні системи Windows працюють на платформах x86, x86-64, IA-64, ARM. Найбільш сучасною операційною системою з сімейства Windows є Windows 7. В березні 2012 року частка Windows 7 серед операційних систем, що використовуються у світі склала 49,9%, тим самим, ця операційна система знаходиться на першому місці в світі по використанню, перевершивши в серпні 2011 року за цим показником попереднього лідера  Windows XP.

Windows 7  операційна система сімейства Windows NT, наступна за Windows Vista. У лінійці Windows NT система носить номер версії 6.1 (Windows 2000 − 5.0, Windows XP − 5.1, Windows Server 2003 − 5.2, Windows Vista і Windows Server 2008 - 6.0). Серверної версією є Windows Server 2008 R2, версією для інтегрованих систем (побудованих з компонентів Windows)  Windows Embedded Standard 2011 (Quebec), мобільного - Windows Embedded Compact 2011 (Chelan, Windows CE 7.0).

Операційна система Windows є однією з найбільш перспективною платформою для написання прикладних програм для настільних ПК [16].

2 Спеціальна частина

2.1 Завдання трасування провідних покрить

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

Основними обмеженнями завдання трасування являються неприпустимість перетину в одному шарі провідників різних ланцюгів і метричні обмеження, зв’язані з обмеженим об'ємом монтажного пространства і певними розмірами трас покриттів, що проводять.

Функція якості монтажу в загальному випадку повинна враховувати наступні параметр: сумарну довжину з’єднань; число додаткових між шарових переходів; число кутів в з'єднаннях; взаємні наведення трас різних ланцюгів; число шарів покриттів, що проводять.

Результат рішення задачі трасування залежить не лише від вживаного алгоритму прокладення трас, але і від рішення ряду пов'язаних між собою завдань. Можна виділити чотири базові завдання [28].

1 Складання списку з'єднань.

2 Розподіл з'єднань по шарах.

3 Визначення порядку трасування.

4 Проведення з'єднань.

Таким чином, для визначення трас з'єднань мають бути отримані відповіді на питання: що? де? коли? і як?

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

Для визначення, коли проводити трасу кожного із з'єднань, списки з'єднань упорядковуються по деяких параметрах.

Як проводити трасу чергового з'єднання, визначає алгоритм прокладення трас.

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

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

Великого поширення набули друковані плати, в яких між шарові з'єднання друкарських провідників здійснюються металізацією наскрізних отворів. Методи машинного проектування таких плат, хоча і мають відмінності, в основному базуються на методах проектування двошарових друкованих плат з додатковими між шаровими переходами. Тому основна увага приділена завданню проектування друкарських з’єднаннями двошарових плат.

У загальному випадку алгоритм, вживаний для прокладки трас, повинен:

— визначати трасу мінімальної довжини, задовільняющий вимогам технології і мінімально заважающею проведенню наступних з'єднань;

— передбачати наступні обмеження: максимальну довжину, ширину траси, що змінюється, можливість обходу околиць спеціально вказаних трас і тому подібне;

— враховувати обмежений об'єм пам'яті машини і час обчислень;

— легко перебудовуватися для вирішення завдань майбутніх проектів.

Проте, головною вимогою до рішення задачі трасування є забезпечення проведення найбільшого числа з'єднань із заданих при обмежених розмірах монтажного простору.

Спільне рішення задачі розміщення і трасування доки практично не реалізовується. Проте в деяких випадках є можливість об'єднати ці завдання. Один з методів спільного рішення завдань розміщення і трасування, запропонований Р. І. Шейнаускасом.

Більшість рішень задачі трасування заснована на канальному представленні монтажного простору або Ли [на алгоритмі 32], згодом названому хвилевим [9].

Алгоритм Ли визначає шлях між двома клітинами (осередками) A і B дискретних грат. Для оцінки якості шляху задається багатовимірна вагова функція F=(f1, f2, ...__

У алгоритмі чітко виділяються дві частини: поширені хвилі і проведення шляху.

При поширенні хвилі, починаючи з осередку A, осередкам, сусіднім з раніше розглянутими, окрім заборонених, привласнюється певне значення маси, т. е. формується новий фронт хвилі. Ця процедура триває до тих пір, поки осередку В не буде присвоєно значення маси. Рухом від осередку В до А з монотонно убуваючи ми значеннями маси визначається шлях між осередками A і В з мінімальним значенням функції F. Шлях виходить оптимальним за декількома показниками з явним пріоритетом між цими показниками.

Для спрощення процедури проведення шляху при поширенні хвилі осередкам привласнюються путні координати, т. е. вказуються напрями, протилежного напряму поширення хвилі в осередку. Геометрія шляху залежить від форми і відношення сусідства осередків. Ли [в роботі 32] набута квадратної форми осередків. І сусідніми вважаються осередки квадрати із загальним ребром. Така модель дискретних грат відповідає ортогональному монтажному простору.

Різні модифікації хвилевого алгоритму [2, 9, 13, 25, 30] запропоновані для з'єднання усіх контактів комплексу, трасування в багатошаровому монтажному просторі, паралельній оптимізації шляху по декількох параметрах, зменшення часу обчислень і необхідного об'єму оперативної пам'яті ЕОМ.

У роботі Рябова [19] запропоновані цікаві модифікації для зменшення часу поширення хвилі. У першій з них хвиля поширюється до мети по двох напрямах. У разі блокування чергового фронту поширення хвилі наступний фронт формується поширенням по чотирьох напрямах. У іншій модифікації є декілька переважних напрямів, які можуть мінятися в залежності від співвідношення координат даної ячейки і цілі.

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

Алгоритми, що використовують хвилевий принцип, слід визнати самими універсальними серед локально оптимальних алгоритмів трасування. Проте їх реалізація на ЕОМ, за винятком простих модифікацій, викликає деякі труднощі із за великого об'єму оперативної пам'яті машини, необхідного для відображення дискретного монтажного простору, і довгої процедури поширення хвилі. У зв'язку з цим було розроблено декілька алгоритмів з меншими можливостями, але в деякій мірі простіших при їх реалізації.

Серед них виділяється запропонований Штейном [23] теоретично цікавий алгоритм для мінімізації числа кутів при виборі конфігурації зв'язуючого дерева комплексу з додатковими вершинами з’єднань. Алгоритм в принципі відрізняється від хвильового. Для одного комплексу будується граф, ребра якого можливі шляхи проведення трас з'єднань, що утворюються вільними відрізками магістралей монтажного простору. Отриманий таким чином граф має зазвичай порівняно велику потужність, і побудову на нім дерева, що реалізовує електричний ланцюг, вимагало б великої кількості вичисленій.

Для зменшення потужності графа застосовується процедура мажорування, що значно спрощує ісходний граф. Після приведення відповідної графу булевої функції зв'язності до диз'юнктивної нормальної форми і отримання з неї найкоротших кон'юнкцій виходять конфігурації простих дерев з мінімальним числом використовуваних магістралей і, тим самим, кутів. З усіх простих дерев в якості рішення можна вибрати дерево, оптимальне по якому не будь іншому показнику. Проте при побудові простих (у сенсі кутів) дерев на платах з існуючими перешкодами сумарна довжина їх з'єднань може значно перевищувати оптимальне значення. Гідністю алгоритму при його реалізації є скорочення об'єму оперативної пам’яти. Час обчислень із за трудомісткої процедури мажорування [4] сумірно з часом виконаних хвилевого алгоритму.

Скоротити час рішення задачі трасування можна, послідовно застосовуючи два алгоритми: евристичний і хвилевий. Евристичні алгоритми вимагають значно менше обчислень, чим будь які модифікації хвилевого алгоритму. Шостак [24] вказує і інша перевага таких алгоритмів. Виявляється, що ручне проведення 1% не проведених хвилевим алгоритмом з'єднань може бути складнішим (або навіть неможливим без повної переробки креслення трасування), ніж ручне проведення 20% з'єднань, не проведених за допомогою евристичного алгоритму. Це пояснюється тим, що за допомогою евристичних алгоритмів зазвичай визначаються тільки траси простих конфігурацій без обходу перешкод і на монтажній площині залишається досить місця для ручного проведення трас інших з'єднань.

Мабуть, перші відомості про евристичний алгоритм, що використовує горизонтальні і вертикальні напрями провідників, опубліковані в роботі Гемблина, Джекобса і Тунісу [19]. У разі неможливості з'єднання двох точок по півпериметру мінімального прямокутника, що покриває ці точки, проводиться сканування цього прямокутника для находження вільних горизонтальних і вертикальних відрізків, що становлять трасу з двома кутами.

Алгоритм мало поворотного шляху, запропонований в [15], перевіряє усі одноповоротні, усе найкоротші двохповоротні, частина триповоротних і чотирьохповоротних шляхів. Введені поняття горизонтальних і вертикальних плечей, що дозволяють звузити зону пошуку і скоротити час рішення задачі. Горизонтальними плечима названі вільні горизонтальні відрізки максимальної довжини, що проходять через контакти, що сполучаються, у напрямі контактів цілей. Вертикальним перерізом названа сукупність вертикальних відрізків, що сполучають горизонтальне плечі. Аналогічно визначаються вертикальні плечі і горизонтальні перерізи. Пошуком вільних відрізків у вертикальному і горизонтальних січеннях вичерпуються можливості визначення усіх двохповоротних шляхів найкоротшої довжини.

Для визначення частини триповоротних і чотирьохповоротних шляхів вводиться пошук вільних відрізків в перерізах між горизонтальними і вертикальними плечима в прямокутнику збільшених розмірів. Таким образом вдається знайти частину трас з обхідними шляхами. При з'єднанні вершин комплексу застосовується алгоритм Прима [17], і при виборі чергової підключеної вершини враховуються відстані не лише до сполучених вершин, але і до точок повороту проведеного з'єднання. При проведенні трас одного ланцюга допускається збіг різних відрізків трас. Таким чином, з'являється можливість включення додаткових вершин під'єднування в сполучаючи дерево.

Найбільш універсальним (серед евристичних) в сенсі можливостей проведення з'єднань слід визнати так звані променеві алгоритми.

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

Один з таких алгоритмів запропонований Лазаревой [11, 12]. На полі двошарової друкованої плати кожному горизонтальному (вертикальному) ряду контактів модулів інтегральних схем ставиться у відповідність совокупність горизонтальних (вертикальних) магістралей, по кожній з яких можливе проведення друкарського провідника до контактів цього ряду. Сукупність таких магістралей називається каналом, а їх число пропускною спроможністю каналу. Для усіх ланцюгів строяться ортогональні мережі і підраховуються очікувані відносні завантаження каналів. Потім для кожної цепи на її ортогональній мережі будується мінімальне зв'язуюче дерево методом хвилі. При побудові дерева мінімізується довжина його гілок і забезпечується рівномірне завантаження каналів з урахуванням ланцюгів, що ще не трасують. Це досягається привласненням кожному ребру досліджуваної мережі вагового коефіцієнта, який враховує максимальне завантаження і мінімальну пропускну спроможність ділянки каналу, совпадающого з цим ребром, а також довжину цього ребра. Після побудови зв’язуючих дерев для усіх ланцюгів виконується розподіл провідників усередині каналів по магістралях, що забезпечує мінімальне число міжшарових переходів.

Подальший розвиток [8] алгоритму Лазаревой дозволяє зменшити число кутів при побудові дерева методом хвилі і поліпшити процес розподілу провідників усередині каналів по магістралях.

Ідеї канального представлення друкованої плати зложених в роботах Базилевича [3]. При приймання різногабаритних елементів друкована плата розбивається на трикутники [3]. При регулярній структурі поля розміщення плата розбивається на прямокутні канали, які в [3] названі макродискретамн. Основна відмінність від модифікації алгоритму Лазаревой [12] полягає в тому, що порядок проходження макродискретів провідниками визначається під час трасування.

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

Подимов і Рощин [16] описують алгоритм трасування з послідовним розподілом ресурсів плати, в якому використаний метод крокуючого отвір. Уся робоча область плати розбивається на три частини: розглянуту, усередині якої трасування завершена; вільну, т. е. ще не розглянуту, і активну (зону отвору), розділяючи розглянуту і вільну частині. Завдання розподілу ресурсів вирішується усередині активної зони.

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

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

Паралельність дослідження трас різних зв’язків знаходиться в методі оцінок [6, 7, 14, 24]. Спочатку при визначенні трас з'єднань допускається їх взаємний перетин або порушення інших обмежень. Для кожного з'єднання підраховується ціна, яка залежить від місця траси, числа перетинів, відстаней і т. п. Процес є ітераційним, і кожного разу виключаються траси з'єднання з найбільшою ціною.

У роботі Гінзбурга та ін. [5] описується наступна модифікація такого методу. Для кожного комплексу будується зв’язуючи дерево рішенням задачі Штейнера. Отримані з'єднання розкладаються по шарах так, щоб траси в одному шарі не перетиналися. Непроведенні ланцюги трасуються, що залишилися, евристичним алгоритмом без урахування взаємних накладень і перетинів. Потім вибирається максимальної число ланцюгів, що не перетинаються. Ланцюги, що залишилися, проводяться за допомогою хвилевого алгоритму.

У роботі [24] усі ланцюги також будуються на одній площині. Проте тут для кожного комплексу будується локально оптимальне зв’язуючи дерево, мінімально конфліктуючи із вже побудованими зв’язками і що не перевищує допустимої довжини. Потім ланцюги прокладаються наново з метою зменшення конфліктів. Для одного шару виділяється група не конфліктуючих з'єднань.

У роботах Гольдиной і Ландау [6, 7] описаний алгоритм, заснований на методі оцінок, що враховують ще не прокладені провідники. Кожен відрізок, з’єднує контакти, характеризується оцінкою, величина якій залежить від довжини і кількості перетинів з іншими відрізками. Дерева з'єднань комплексів визначаються так, щоб мінімізувати суму усіх оцінок. Одночасно проводиться розподіл відрізків по шарах.

У роботі Рябова і Млинцевою [19] запропонований динамічний підхід до завдання трасування. Для чергового комплексу методом поширення хвилі будується зв'язна безліч осередків дискретного поля. Збудована область піддається безперервним топологічним перетворенням розширення і стискування [18]. Кожна траса між двома нерухомими точками розглядується як область, і, отже, розширюється і стискується. Цими перетвореннями досягається рівномірність розташування трас, і виходять їх різні метричні варіанти.

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

У роботі [22] для коригування раніше проведених трас пропонується стирати фрагменти, проведення досліджуваного з'єднання, що заважають, і проводити їх заново.