Спосіб впорядкованого доступу до даних в пам’яті та пристрій для його реалізації

Реферат: Спосіб впорядкованого доступу до даних в пам′яті та пристрій пам′яті належать до області обчислювальної техніки і можуть бути використані при побудові пристроїв пам'яті. Винахід полягає в тому, що в способі впорядкованого доступу до даних в пам'яті, до якої в режимі запису записують дані, сформовані в масив, зберігають ці дані, та в режимі зчитування зчитують дані, сформовані в масив, відповідно до винаходу, кожному даному привласнюють індекс, за числовим значенням якого визначається місце цього даного в масиві вихідних даних, опрацьовують індекси, визначають код впорядкування, який для даного набору індексів однозначно вказує розміщення вхідних даних в масиві вихідних даних відповідно до числових значень їх індексів, та за значенням цього коду впорядковують масив вхідних даних, формуючи масив вихідних даних, причому код впорядкування визначають в пам'яті перед або одночасно з виконанням впорядкування масиву вхідних даних, для чого записують індекси до пам'яті та проводять їх опрацювання або визначають заздалегідь, проводячи розрахунки чи моделювання, та подають цей код ззовні або будують пам'ять таким чином, щоб вона здійснювала впорядкування даних відповідно до цього коду. За допомогою запропонованого винаходу досягається розширення функціональних можливостей доступу до пам’яті, а саме забезпечується довільний доступ до пам’яті. UA 104218 C2 (12) UA 104218 C2 UA 104218 C2 5 10 15 20 25 30 35 40 45 50 55 Винахід належить до області обчислювальної техніки і може бути використаний при побудові пристроїв пам'яті. Відомий спосіб асоціативного доступу до даних в пам'яті, яка складається з комірок, до яких в режимі запису записують дані з вхідних портів, зберігають ці дані, та в режимі зчитування зчитують дані на вихідні порти, відповідно до якого дані записують в довільні вільні (звільнені) комірки і з пам'яті дане вибирають за значенням його ознаки, яку записують в комірку разом з цим даним, для чого до складу пам'яті вводять пристрій пошуку даного та виконують операцію порівняння шуканої ознаки з усіма записаними до пам'яті ознаками і, тим самим, знаходять місце розміщення даного, яке підлягає зчитуванню, [Угрюмов Е.П. Цифровая схемотехника. /Е.П.Угрюмов // - СПб.: БХВ - Санкт-Петербург. 2000. - 528 с; стор.182]. В якості ознаки може бути і значення самого даного. Недоліками способу асоціативного доступу до даних в пам'яті є необхідність двократного звернення до однієї комірки - при запису і при зчитуванні даного, а також необхідність забезпечення доступу до кожної комірки з входу та виходу пам'яті або з об'єднаного входу/виходу пам'яті, причому при зчитуванні необхідно проводити порівняння шуканої ознаки з ознаками наявних у пам'яті даних, що вимагає великих затрат на елементи доступу та сповільнює роботу пам'яті. Відомий спосіб адресного доступу до даних в пам'яті, яка складається з комірок та засобів адресного доступу до кожної комірки, до яких в режимі запису записують дані з вхідного порту, зберігають ці дані, та в режимі зчитування зчитують дані на вихідний порт, відповідно до якого разом із кожним даним при його запису в пам'ять та при його зчитуванні з пам'яті подають адресу комірки пам'яті (її номер), яка ідентифікує цю комірку, з тим, щоб за допомогою засобів адресного доступу до кожної комірки здійснити запис даного до цієї комірки або його зчитування з цієї комірки [Мельник А.О. Архітектура комп'ютера. / А.О. Мельник // - Луцьк. Волинська обласна друкарня, 2008. - 470 с; стор. 309, 310, 331-334]. Спосіб адресного доступу до даних в пам'яті найширше використовується в сучасних комп'ютерах. Недоліки відомого способу доступу до даних - неможливість паралельного доступу до даних з багатьох портів та необхідність зберігання адрес комірок пам'яті, до яких записані дані, для того, щоб при потребі ці дані можна було знайти та зчитати, а також необхідність подачі адреси на адресний вхід пам'яті як при запису даного, так і при його зчитуванні. Відомий спосіб послідовного доступу до даних в пам'яті, яка складається з комірок, до яких в режимі запису записують дані з вхідних портів, зберігають ці дані, та в режимі зчитування зчитують дані на вихідні порти, коли записані в комірки пам'яті дані утворюють деяку чергу [Угрюмов Е.П. Цифровая схемотехника. / Е.П. Угрюмов // - СПб.: БХВ - Санкт-Петербург. 2000. 528 с; стор. 181, 189-190]. Зчитування даних з черги здійснюється послідовно одне за одним в порядку запису або в зворотному порядку. Прямий порядок зчитування забезпечується пам'яттю FIFO з дисципліною обслуговування "перший прийшов-перший вийшов" (First In - First Out), а також в файлових і циклічних запам'ятовуючих пристроях. Обернений порядок зчитування забезпечується пам'яттю LIFO з дисципліною обслуговування "останній прийшовперший вийшов" (Last In - First Out). Однак цей спосіб послідовного доступу до даних в пам'яті є низькі функціональні можливості, так як він не забезпечує іншого, крім послідовного, порядку доступу до даних. В основу винаходу поставлено задачу створити спосіб впорядкованого доступу до даних в пам'яті шляхом забезпечення довільного впорядкованого доступу до даних і, тим самим, розширити функціональні можливості. Поставлена задача вирішується тим, що в способі впорядкованого доступу до даних в пам'яті, до якої в режимі запису записують дані, сформовані в масив, зберігають ці дані, та в режимі зчитування зчитують дані, сформовані в масив, відповідно до винаходу, кожному даному привласнюють індекс, за числовим значенням якого визначається місце цього даного в масиві вихідних даних, опрацьовують індекси, наприклад проводять сортування за зростанням або за спаданням їх числових значень, визначають код впорядкування, який для даного набору індексів однозначно вказує розміщення вхідних даних в масиві вихідних даних відповідно до числових значень їх індексів, та за значенням цього коду впорядковують масив вхідних даних, формуючи масив вихідних даних, причому код впорядкування визначають в пам'яті перед або одночасно з виконанням впорядкування масиву вхідних даних, для чого записують індекси до пам'яті та проводять їх опрацювання, або визначають заздалегідь, проводячи розрахунки чи моделювання, та подають цей код ззовні або будують пам'ять таким чином, щоб вона здійснювала впорядкування даних відповідно до цього коду. 1 UA 104218 C2 5 10 15 20 25 30 35 40 45 Ефективність запропонованого способу впорядкованого доступу до даних в пам'яті визначається тим, що, на відміну від прототипу, його реалізація дозволяє розширити функціональні можливості пам'яті, так як він забезпечує не лише послідовний, а й будь-який інший, тобто довільний порядок доступу до даних. Перед розглядом питання реалізації способу впорядкованого доступу до даних в пам'яті опишемо вхідні дані, їх індекси та вихідні дані. Масив вхідних даних, які записують до пам'яті, має вигляд матриці D0,0 D0,1 ... D0,l1 D1,0 D1,1 ... D1,l1 , ... Dk 1,0 Dk 1,1 ... Dk 1,l1 де IDi,j - вхідне дане, яке знаходиться в і-му рядку (і = 0,1,...k-1) та j-му стовпці (j = 0,1,...l-1) матриці вхідних даних. Масив індексів, які привласнюють кожному даному, та за їх величиною впорядковують дані в пристрої впорядкування даних, має вигляд матриці S  D 0, 0 SD0,1 ... SD 0,l1 SD1,0 SD1,1 ... SD1,l1 , ... SDk 1,0 SDk 1,1 ... SDk 1,l1 де SIDi,j - індекс вхідного даного IDi,j, яке знаходиться в і-му рядку (і = 0,1,...k-1) та j-му стовпці (j = 0,1,...l-1) матриці вхідних даних. Масив вихідних даних, які зчитують з пам'яті, має вигляд матриці OD 0,0 OD 0,1 ... OD 0,n1 OD 1,0 OD 1,1 ... OD 1,n1 , ... OD m1,0 OD m1,1 ... OD m1,n1 де ODs,t - вихідне дане, яке знаходиться в s-му рядку (s = 0,1,...m-1) та t-му стовпці (t = 0,1,.. .n1) матриці вихідних даних. На фіг. 1 зображена схема пристрою пам'яті з впорядкованим доступом, на фіг.2 - структура сортувальної мережі для восьми входів та восьми виходів, на фіг.3 - структура базового елемента сортувальної мережі, на фіг.4 - структура комутуючої мережі для восьми входів та восьми виходів, на фіг. 5 - структура базового елемента комутуючої мережі. Спосіб впорядкованого доступу до даних в пам'яті реалізується наступним чином. Структура пристрою, який реалізує запропонований спосіб впорядкованого доступу до даних в пам'яті, показана на фіг. 1. Назвемо цей пристрій пам'яттю з впорядкованим доступом (ПВД). Пам'ять з впорядкованим доступом містить Μ комірок пам'яті (10,0, 10,1, ..., 1k-1, l-1), для зберігання даних та їх індексів, де M=kl, k - КІЛЬКІСТЬ даних в стовпці матриці вхідних даних, l КІЛЬКІСТЬ даних в рядку матриці вхідних даних, пристрій впорядкування даних (2), Μ вихідних вентилів (30,0, 30,1, ..., 3m-1,n-1), де М=mn, m - кількість даних в стовпці матриці вихідних даних, n кількість даних в рядку матриці вихідних даних, лічильники (4) та (5), дешифратори (6) з виходами (60, 61, ..., 6k-1), та (7) з виходами (70, 71, ... 7m-1), 1 інформаційних входів ( 80, 81, ... 8l-1), n інформаційних виходів (90, 91, ... 9n-1), вхід (10) запису, вхід (11) зчитування, вхід (12) керування пристрою впорядкування даних (2), причому входи комірок пам'яті (1i,0, 1i,1, ..., 1i, l-1), де і = 1,2,…, k-1 з'єднані з відповідними інформаційними входами (80, 81, ... 8l-1), виходи комірок пам'яті (10,0, 10,1, ..., 1k-1,l-1) з'єднані з входами пристрою впорядкування даних (2), виходи якого від 0-го до (М-1)-го з'єднані з входами вихідних вентилів (30,0, 30,1, ..., 3m-1,n-1), де М=mn, m кількість даних в стовпці матриці вихідних даних, n - кількість даних в рядку матриці вихідних даних, виходи вихідних вентилів (3j,0,3j,1, ...3j,n-1), де j = 1,2, ... m-1, з'єднані з інформаційними виходами (90, 91, ... 9n-1), пам'яті, вхід (10) запису з'єднаний з входами запису комірок пам'яті та з входом лічильника (4), вихід якого з'єднаний з входом дешифратора (6), виходи (60, 61 ... 6к-і) якого з'єднані з відповідними входами дозволу запису комірок пам'яті (1i,0, 1i,1, ..., 1i,l-1), де і = 1,2,…, k-1, вхід (11) зчитування з'єднаний з входами зчитування вихідних вентилів та з входом лічильника (5), вихід якого з'єднаний з входом дешифратора (7), виходи (70, 71, ... 7m-1), якого з'єднані з відповідними входами дозволу зчитування вихідних вентилів (3j,0,3j,1, ...3j,n-1), де j = 1,2, ... m-1, вхід (12) з'єднаний з входом керування пристрою впорядкування даних (2). 2 UA 104218 C2 5 10 15 20 25 30 35 40 45 50 55 Пам'ять з впорядкованим доступом залежно від типу використовуваного пристрою впорядкування даних (2) може бути реалізована в чотирьох варіантах. В першому варіанті ПВД, відповідно до запропонованого способу впорядкованого доступу до даних в пам'яті, код впорядкування визначають одночасно з виконанням впорядкування масиву вхідних даних в пристрої впорядкування даних (2). В другому варіанті ПВД, відповідно до запропонованого способу впорядкованого доступу до даних в пам'яті, код впорядкування визначають перед виконанням впорядкування масиву вхідних даних в пристрої впорядкування даних (2). В третьому варіанті ПВД, відповідно до запропонованого способу впорядкованого доступу до даних в пам'яті, код впорядкування визначають заздалегідь шляхом проведення розрахунків чи моделювання, та подають цей код на пристрій впорядкування даних ззовні. В четвертому варіанті ПВД, відповідно до запропонованого способу впорядкованого доступу до даних в пам'яті, код впорядкування визначають заздалегідь шляхом проведення розрахунків чи моделювання та створюють пристрій впорядкування даних, входи якого з'єднані з виходами відповідно до цього коду. Пам'ять з впорядкованим доступом працює наступним чином. В пам'яті з впорядкованим доступом, яка реалізована за першим варіантом, виконуються наступні дії. Першою дією є запис в комірки пам'яті вхідних даних та їх індексів. Сигналом запису з входу (10) вхідні дані та їх індекси запишуться у відповідні комірки пам'яті, причому місце запису даних та індексів вказується кодом з виходу лічильника (4), на основі якого дешифратор (6) формує сигнали дозволу запису. Лічильник (4) спочатку перебуває в стані «0» та дозволяє запис першого рядка даних і їх індексів до комірок пам'яті (10,0, 10,1, ..., 10,l-1), після поступлення першого сигналу запису з входу (10) запису переходить в стан «1» та дозволяє запис другого рядка даних і їх індексів до комірок пам'яті (10,0, 10,1, ..., 11, l-1), після поступлення другого сигналу запису з входу (10) запису переходить в стан «2» та дозволяє запис третього рядка даних і їх індексів до комірок пам'яті (12,0, 12,1, ..., 12,l-1) і так до запису k-го рядка даних і їх індексів до комірок пам'яті (1k-1,0, 1k-1,1, ..., 1k-1, l-1). Другою дією є впорядкування в пристрої впорядкування даних (2) масиву вхідних даних з комірок пам'яті (10,0, 10,1, ..., 1k-1,l-1), за числовими значеннями їх індексів у масив вихідних даних та подача цих даних на входи вихідних вентилів (30,0, 30,1, ..., 3m-1,n-1). При цьому проводять сортування індексів в пристрої впорядкування даних за деяким правилом, наприклад за зростанням або за спаданням їх числових значень, визначають код впорядкування, який для даного набору індексів однозначно вказує пристрою впорядкування даних яким чином з'єднати його входи з виходами з тим, щоб розмістити кожне вхідне дане в масиві вихідних даних відповідно до числових значень їх індексів, та за значенням цього коду впорядковують в пристрої впорядкування даних масив вхідних даних формуючи масив вихідних даних. Цей процес для випадку, коли використовують правило впорядкування даних за зростанням числових значень їх індексів, описується наступним чином: Нехай SV0,0 SV0,1 ... SV0,r 1 SV1,0 SV1,1 ... SV1,r 1 , ... SVp 1,0 SVp 1,1 ... SVp 1,r 1 - матриця відсортованих індексів вхідних даних така, що SV0,0< SV0,1 < SV0,2 ··· SID1, то на виході схеми порівняння (18) буде сигнал 0, який пропускає через мультиплексор (21) дане ID0 та індекс SID0, а через мультиплексор (22) - дане ID1 та індекс SID1. Якщо індекс даного ID0 менший від індексу даного ID1, тобто SID0 SID1, то на виході схеми порівняння (18) буде сигнал 0, який пропускає через мультиплексор (21) індекс SID0, а через мультиплексор (22) - індекс SID1. Якщо індекс даного ID0 менший від індексу даного ID1, тобто SID0 < SID1, то на виході схеми порівняння (18) буде сигнал 1, який пропускає через мультиплексор (21) індекс SID1, а через мультиплексор (22) - індекс SID0. Тобто, в даному режимі базовий елемент виконує функції елемента сортувальної мережі, яка сортує індекси вхідних даних. З переходом потенціалу на вході керування (12) в одиницю значення сигналу з схеми порівняння (18) фіксується в тригері (19). Тим самим відбувається налаштування базового елемента (13) на роботу в режимі впорядкування. Після цього на вході керування (12) в цьому режимі потенціал рівний одиниці і не змінюється, а тригер (19) більше не перемикається. Сигнал з його виходу, проходячи через мультиплексор (20), утримує мультиплексори (21) та (22) в режимі впорядкування, який в подальшому уже не залежить від значень даних на входах базового елемента. Тобто після подачі вхідних даних ID0 та ID1 вони впорядковуються відповідно до значення Їх індексів, і, таким чином, формуються вихідні дані OD0 та OD1. В пам'яті з впорядкованим доступом, реалізованій за третім варіантом, виконуються наступні дії. Як пристрій впорядкування даних (2) пам'яті з впорядкованим доступом, реалізованій за третім варіантом, може бути використана комутуюча мережа, наприклад комутуюча мережа описана в [Мельник А.О. Архітектура комп'ютера. /А.О. Мельник // - Луцьк. Волинська обласна друкарня, 2008. - 470 с; стор. 461], структура якої для восьми входів та восьми виходів показана на фіг.4. Комутуючу мережу будують на основі базових елементів (23), які здійснюють впорядкування двох даних та з'єднані між собою відповідно до схеми мережі. Структура базового елемента такої комутуючої мережі наведена на фіг. 5. До складу базового елемента входять два двовходових мультиплексори (24) та (25) з входами (26), (27) та виходами (28), (29). На два входи (26) та (27) базового елемента (23) паралельно надходять два даних ID0 та ID1. Кодом з входу керування (12) задається варіант перестановки даних в комутуючій мережі. Один з розрядів цього коду 12і, де і - кількість розрядів коду, надходить на керуючі входи мультиплексорів (24) та (25) і задає їм один з двох варіантів комутації - прямо або навхрест. Сигнал 0 з входу 12і пропускає через мультиплексор (24) на вихід (28) дане ID0, а через мультиплексор (25) на вихід (29) - дане ID1. Сигнал 1 на вході 12і пропускає через мультиплексор (24) на вихід (28) дане ID1, а через мультиплексор (25) на вихід (29) - дане ID0. Пристрій впорядкування даних (2) пам'яті з впорядкованим доступом, реалізованій за четвертим варіантом створюють за заздалегідь визначеним кодом впорядкування, з'єднавши його входи з виходами відповідно до цього коду. ФОРМУЛА ВИНАХОДУ 50 55 1. Спосіб впорядкованого доступу до даних в пам'яті, до яких в режимі запису записують дані, сформовані в масив, зберігають ці дані, та в режимі зчитування зчитують дані, сформовані в масив, який відрізняється тим, що кожному даному привласнюють індекс, за числовим значенням якого визначають місце цього даного в масиві вихідних даних, опрацьовують індекси, наприклад проводять сортування за зростанням або за спаданням їх числових значень, визначають код впорядкування, який для даного набору індексів однозначно вказує розміщення вхідних даних в масиві вихідних даних відповідно до числових значень їх індексів, та за значенням цього коду впорядковують масив вхідних даних, формуючи масив вихідних даних, причому код впорядкування визначають в пам'яті перед або одночасно з виконанням впорядкування масиву вхідних даних, для чого записують індекси до пам'яті та проводять їх опрацювання або визначають заздалегідь, проводячи розрахунки чи моделювання, та подають 6 UA 104218 C2 5 10 15 20 цей код ззовні або будують пам'ять таким чином, щоб вона здійснювала впорядкування даних відповідно до цього коду. 2. Пристрій пам'яті з впорядкованим доступом містить Μ комірок пам'яті (10,0, 10,1,..., 1k-1,l-1), де M=kl, k - кількість даних в стовпці матриці вхідних даних, l - кількість даних в рядку матриці вхідних даних, вхід (10) запису, з'єднаний з входами запису комірок пам'яті, вхід (11) зчитування комірок даних, який відрізняється тим, що містить пристрій впорядкування даних (2), Μ вихідних вентилів (30,0, 30,1,..., 3m-1,n-1), де М=mn, m - кількість даних в стовпці матриці вихідних даних, n - кількість даних в рядку матриці вихідних даних, лічильники (4) та (5), дешифратори (6) з виходами (60, 61,..., 6k-1), та (7) з виходами (70, 71, ..., 7m-1), l інформаційних входів (80, 81,..., 8l-1), n інформаційних виходів (90, 91,..., 9n-1), вхід (12) керування пристрою впорядкування даних (2), причому входи комірок пам'яті (1i,0, 1i,1,..., 1i,l-1), де і=1,2,…, k-1, з'єднані з відповідними інформаційними входами (80, 81,..., 8l-1), виходи комірок пам'яті (10,0, 10,1,..., 1k-1,l-1), з'єднані з входами пристрою впорядкування даних (2), виходи якого від 0-го до (М-1)-го з'єднані з входами вихідних вентилів (30,0, 30,1,..., 3m-1,n-1), виходи вихідних вентилів (3j,0, 3j,1,..., 3j,n-1), де j=1, 2,...m-1, з'єднані з інформаційними виходами (90, 91,..., 9n-1) пам'яті, вхід (10) запису з'єднаний з входом лічильника (4), вихід якого з'єднаний з входом дешифратора (6), виходи (6 0, 61,..., 6k-1) якого з'єднані з відповідними входами дозволу запису комірок пам'яті (1 i,0, 1i,1,..., 1i,1-1), де і=1, 2,…, k-1, вхід (11) зчитування з'єднаний з входами зчитування вихідних вентилів та з входом лічильника (5), вихід якого з'єднаний з входом дешифратора (7), виходи (7 0, 71,..., 7m-1) якого з'єднані з відповідними входами дозволу зчитування вихідних вентилів (3 j,0, 3j,1,..., 3j,n-1), де j=1, 2,..., m-1, вхід (12) з'єднаний з входом керування пристрою впорядкування даних (2). 7 UA 104218 C2 8 UA 104218 C2 Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 9