івнює нулю, і ця ймовірність мала. Це означає, що для великих значень n твір слабо заповнених матриць цією властивістю володіти не буде. Імовірність того, що елемент матриці C не дорівнює нулю, можна порахувати за формулою:
При n=100 і p=0,1 ймовірність=0,634, але при n=1000 вона практично наближається до одиниці і дорівнює 0,9999.
Ситуація змінюється, якщо ймовірність p є спадною функцією від n. Припустимо, наприклад, p=1/n, тоді
Враховуючи обидва цих співвідношення, можна сформулювати наступне твердження:
Якщо при множенні слабо заповнених матриць A і B ймовірність ненульового елемента p постійна, то із зростанням розміру матриць n ймовірність заповнення результуючої матриці C прагне до одиниці.
Якщо при множенні слабо заповнених матриць A і B ймовірність ненульового елемента p залежить від n і дорівнює 1/n, то результуюча матриця C також є слабо заповненою з тією ж імовірністю заповнення, як і вихідні матриці.
Підіб'ємо підсумок. З тверджень випливає, що розумно будувати різні алгоритми, для випадку, коли твір множимо матриць є щільно заповненою матрицею, і для випадку, коли цей твір є слабо заповненою матрицею.
1.4 Проблематика паралельних обчислень
Для паралельних обчислень властиво більш складна архітектура побудови програм, ніж для послідовних. Відповідно, при організації обчислень доводиться стикатися з такими труднощами як: доступ до ресурсів, синхронізація виконання, поділ роботи.
До основних проблем паралельних обчислень можна віднести наступні:
· Гонка даних;
· взаімоблокіровке;
· Синхронізація.
Під гонкою даних в паралельному програмуванні розуміється така ситуація, коли два і більше потоку працюють із загальним ресурсом. Припустимо, що з декількох потоків одночасно ведеться запис в загальну пам'ять. Тоді результат такої операції непередбачуваний, так як він буде визначатися записом останнього з потоків, при цьому результати операцій з інших потоків будуть проігноровані і результат роботи в цілому буде некоректний.
Інший же не менш важливою проблемою є синхронізація потоків виконання. При вирішенні завдань часто можна зіткнутися з необхідністю очікування завершення якої-небудь операцій в одному або декількох потоках, щоб продовжити виконання в іншому. Дана ситуація якраз і характеризує проблему синхронізації.
Для вирішення перерахованих вище проблем були створені спеціальні механізми - засоби синхронізації. До таких механізмів відносяться:
· м'ютексів;
· Критичні секції;
· Бар'єри;
· Семафори;
· Замки.
З рішенням вищеперелічених проблем в паралельних обчисленнях з'являється ще одна не менш важлива ситуація, коли синхронізація і блокування доступу до ресурсів призводить до наступної проблеми - взаімоблокіровке. Взаімоблокіровка може виникнути, коли два і більше потоку намагаються отримати взаємовиключний доступ до множинних загальних ресурсів.
Для вирішення даної проблеми можна використовувати як розмежування блокування доступу на читання і на запис, а так само одноразову блокування всіх загальних ресурсів відразу.
Глава 2. Спеціальна частина
. 1 Вибір програмних засобів
Для розробки дипломного проекту необхідно визначити засоби моделювання та розробки. До основних факторів вибору технології проектування можна віднести наступні:
· Висока продуктивність розробленого додатка;
· Швидкість розробки додатка;
· Низькі вимоги розробленого додатка до ресурсів комп'ютера;
· Можливість розробки нових компонентів та інструментів власними коштами;
· наращиваемость (за рахунок вбудовування нових компонент);
· Зручна опрацювання ієрархії об'єктів.
Виходячи з вище перерахованих критеріїв, для проектування інформаційної підсистеми ми вибрали такі засоби як Enterprise Architect 9 який буде служити для створення моделей, виконання аналізу, документування та планування зміни складних бізнес-процесів і AllFusion Process Modeler ERwin 7 для розробки фізичної моделі даних і бази данних.Architect 9 - CASE-інструмент для проектування і конструювання програмного забезпечення. EA підтримує специфікацію UML 2.0, що описує візуальну мову, яким можуть бути визначені моделі проекту.
К...
