Спосіб паралельної обробки цифрових даних із запобіганням виникненню колізій

Реферат: Спосіб паралельної обробки цифрових даних із запобіганням виникненню колізій включає операції зчитування, обробку даних. При цьому здійснюють безпомилкову паралельну багатоетапну обробку порцій та серій порцій даних із формуванням повідомлень-запитів та стану у відповідності до обробника даних. UA 77050 U (54) СПОСІБ ПАРАЛЕЛЬНОЇ ОБРОБКИ ЦИФРОВИХ ДАНИХ ІЗ ЗАПОБІГАННЯМ ВИНИКНЕННЮ КОЛІЗІЙ UA 77050 U UA 77050 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до області обчислювальної техніки і може бути використаний для цифрової обробки масивів даних в реальному масштабі часу. 7 Відомий спосіб обчислення та обробки даних (пат. России № 2142158С1, МПК G06F 15/00, G06F 15/16, публ. 27.11.1999) призначений для реалізації можливості обчислювальної станції приєднатися до обчислювальної задачі в будь-який час і виконувати свою власну обчислювальну функцію зі своєю швидкістю та покладений в основу системи, яка описана в патенті. Недоліком даного способу є низька оперативність, так як вірогідність звернення обчислювальної станції до задачі створює проблему колізії, рішень якої не вказано. 7 Другий відомий спосіб обчислення і обробки даних (пат. России № 2145438С1, МПК G06F 17/60, публ. 10.02.2000) призначений для комерційних і управлінських специфічних функцій обліку і звітності, що включає операції зчитування вихідних даних виділення даних і їх перетворення. Недоліком даного способу є жорсткість масштабованості та відсутність можливостей інтеграції з Іншими подібними системами. Відомий також, вибраний як найближчий аналог, спосіб обробки цифрових даних (пат. України № 47741 А, МПК (2006) G06F 7/00, G06F 7/38, G06Q 99/00, публ. 15.07.2002, бюл. № 7), що включає зчитування даних, виділення даних і їх обробку. Спосіб передбачає попереднє виділення даних двох послідовностей і двоетапне перетворення даних, коли на першому етапі дані другої послідовності підсумовують, а на другому етапі їх масштабують, при цьому коефіцієнт масштабування визначають як відношення суми даних першої послідовності до суми квантованих даних другої послідовності. Недоліком даного способу є низька оперативність обробки порцій даних системою паралельних обчислень при багатоетапному процесі обробки за рахунок виникнення колізій, що приводить до неможливості їх використання в складних багатоетапних паралельних системах обробки даних. В основу корисної моделі поставлена задача запобігання виникненню колізій при паралельній обробці цифрових даних шляхом використання системи повідомлень стану та повідомлень-запитів. Поставлена задача вирішується тим, що у способі паралельної обробки цифрових даних із запобіганням виникненню колізій, що містить операції зчитування, обробку даних, згідно з корисною моделлю, що здійснюють безпомилкову паралельну багатоетапну обробку порцій та серій порцій даних із формуванням повідомлень-запитів та стану у відповідності до обробника даних (екземпляра програми). Паралельна обробка цифрових даних із запобіганням виникненню колізій дещо збільшує тривалість процесу обробки даних за умови незначної кількості даних при наявності малої кількості обробників (але не менше двох). Однак, у разі виникнення хоча б однієї колізії часові затрати на повторну обробку порції даних більші за часові витрати обробки цифрових даних із запобіганням виникненню колізій. Крім того, згідно з корисною моделлю, загальний час обробки порцій даних відповідає кількості порцій даних поділеної на кількість обробників обчислювальної системи. Спосіб паралельної обробки цифрових даних із запобіганням виникненню колізій працює в децентралізованих обчислювальних системах. Спосіб паралельної обробки цифрових даних із запобіганням виникненню колізій працює в централізованих обчислювальних системах. Заявлений спосіб здійснюється таким чином. Суть корисної моделі пояснюється кресленнями, де Фіг. 1 - узагальнена блок-схема роботи способу, Фіг. 2 - Фіг. 6 - детальні блок-схеми способу. На нульовому етапі обробки, що функціонує на обчислювальній станції, екземпляр програми шукає у вхідному буфері чергову порцію даних серії. При відсутності у вхідному буфері порції даних, екземпляр програми виконує пошуковий цикл повідомлень стану по всім сховищам порцій даних на всіх етапах обробки. При виявленні екземпляром програми у сховищі порцій даних повідомлення стану, яке дозволяє проводити обробку серій (повідомлення стану про сформовану і готову до обробки серію порцій даних), він шукає повідомлення-запит на обробку цієї серії порцій даних. У разі відсутності повідомлення-запиту серії порції даних екземпляр створює в черзі повідомлень-запитІв відповідне повідомлення-запит. При наявності повідомлення-запиту цикл починається спочатку. При виявленні екземпляром програми повідомлення стану, яке не дозволяє проводити обробку серій (до таких повідомлень відносяться: повідомлення стану про формування серії порцій даних; повідомлення про процес обробки серії порцій даних; повідомлення про 1 UA 77050 U 5 10 15 20 25 30 35 40 45 50 завершення обробки серії порції даних), він продовжує пошук у сховищах порцій даних. При відсутності завдань (у всіх сховищах порцій даних серії формуються, обробляються або вже оброблені) екземпляр програми надсилає повідомлення програмі про перехід в режим роботи "Очікування". При надходженні повідомлення від програми про вихід з режиму "Очікування" до закінчення заданого часу, екземпляр програми переходить до початку загального циклу. У разі відсутності повідомлення від програми про вихід із режиму "Очікування" і після закінчення заданого часу, екземпляр програми завершує роботу. При наявності у вхідному буфері порції даних екземпляр програми шукає в черзі повідомлень-запитів повідомлення-запит про ці порції даних. При наявності повідомленнязапиту про порції даних, екземпляр програми переходить до початку загального циклу, а у разі відсутності повідомлення-запиту про порції даних, екземпляр програми створює в черзі повідомлень-запитів відповідне повідомлення-запит. Після цього екземпляр програми очікує заданий час. Потім він шукає в черзі повідомленьзапитів повідомлення-запит про порції даних. При виявленні екземпляром програми декількох повідомлень-запитів, дана порція даних буде переміщена цим екземпляром програми за умови, що номер її повідомлення-запиту менше номерів інших повідомлень-запитів. При тотожності номерів повідомлень-запитів, порція даних буде переміщена цим екземпляром програми за умови, що номер обчислювальної станції, на якій він функціонує, менше номерів інших обчислювальних станцій. Решта екземплярів програми переходять до початку циклу. Після цього екземпляр програми переміщує порцію даних серії з вхідного буфера в сховище порцій даних для першого етапу обробки. Екземпляр програми створює повідомлення стану про формування серії порцій даних з метою запобігання обробки несформованої серії іншим екземпляром програми. Екземпляр програми перевіряє кожну вхідну порцію даних на предмет виявлення останньої із серії. При виявленні чергової (не останньої) порції даних із серії, екземпляр програми переходить до початку циклу. При виявленні останньої порції даних із серії, або, якщо серія містить єдину порцію даних, екземпляр програми створює повідомлення стану про те, що серія порцій даних сформована. Потім він видаляє повідомлення стану про формування серії порцій даних. Екземпляр програми шукає у черзі повідомлень-запитів повідомлення-запит про серію порцій даних. При наявності повідомлення-запиту про серію порцій даних, екземпляр програми переходить до початку загального циклу. При відсутності повідомлення-запиту, екземпляр програми створює в черзі повідомлень-запитів відповідне повідомлення-запит. Функціонуючий на обчислювальній станції, екземпляр програми очікує наперед заданий час. Потім він шукає в черзі повідомлень-запитів повідомлення-запит про серію порцій даних. При виявленні екземпляром програми декількох повідомлень-запитів, дана серія порцій даних буде оброблятися цим екземпляром програми за умови, що номер її повідомлення-запиту менше номерів Інших повідомлень-запитів, а при тотожності повідомлень-запитів, серія порцій даних буде оброблятися цим екземпляром програми за умови, що номер обчислювальної станції, на якій він функціонує, менше номерів інших обчислювальних станцій. Решта екземплярів програми, переходять до початку загального циклу. Екземпляр програми здійснює черговий етап обробки серії порцій даних. Перед початком обробки серії порцій даних екземпляр програми створює в черзі повідомлень стану повідомлення стану про процес обробки даної серії порцій даних. Це запобігає зверненню екземпляра програми з метою обробки цієї ж серії порцій даних, що унеможливлює колізію. Після закінчення обробки серії порцій даних екземпляр програми створює в черзі повідомлень стану повідомлення про закінчення обробки цієї серії порцій даних. Це запобігає зверненню екземпляра програми з метою повторної обробки цієї ж серії порцій даних. Екземпляр програми видаляє повідомлення станупро процес обробки серії порцій даних. Після цього екземпляр програми виконує перевірку етапу обробки на предмет визначення його останнього з кількості етапів обробки порцій даних. Якщо це не останній етап обробки, екземпляр програми переходить до пункту формування нової серії для подальшої обробки, а якщо - останній, то екземпляр програми формує звіт-повідомлення про завершення обробки серії порцій даних на останньому етапі і переходить до початку загального циклу. 55 ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб паралельної обробки цифрових даних із запобіганням виникненню колізій, що містить операції зчитування, обробку даних, який відрізняється тим, що здійснюють безпомилкову 2 UA 77050 U паралельну багатоетапну обробку порцій та серій порцій даних із формуванням повідомленьзапитів та стану у відповідності до обробника даних (екземпляра програми). 3 UA 77050 U 4 UA 77050 U 5 UA 77050 U 6 UA 77050 U 7 UA 77050 U Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 8