ПОТОКОВІ МЕТОДИ І ЗАСОБИ ПОВНОФУНКЦІОНАЛЬНОЇ ПОБІТОВОЇ АРИФМЕТИКИ ЗІ ЗМЕНШЕНИМИ ВИТРАТАМИ ОБЛАДНАННЯ

Короткий опис

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Вінницький національний технічний університет

На правах рукопису

ЧЕРНЯК ОЛЕКСАНДР ІВАНОВИЧ

УДК 681.325

ПОТОКОВІ МЕТОДИ І ЗАСОБИ

ПОВНОФУНКЦІОНАЛЬНОЇ ПОБІТОВОЇ АРИФМЕТИКИ

ЗІ ЗМЕНШЕНИМИ ВИТРАТАМИ ОБЛАДНАННЯ

Спеціальність 05.13.05 – комп’ютерні системи та компоненти

Дисертація на здобуття наукового ступеня кандидата технічних наук

Науковий керівник

АЗАРОВ ОЛЕКСІЙ ДМИТРОВИЧ,

доктор технічних наук, професор

Вінниця – 2012

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ. 4

ВСТУП      7

РОЗДІЛ 1        СТАН ТА ЗАДАЧІ ПОВНОФУНКЦІОНАЛЬНОЇ ПОБІТОВОЇ ПОТОКОВОЇ ОБРОБКИ   17

1.1 Проблема з’єднань. 17

1.2 Використання побітової обробки у сучасних технологіях. 22

1.3 Використання побітової обробки у перспективних технологіях майбутнього  24

1.4 Порозрядна обробка у знакорозрядній двійковій системі числення. 29

1.5 Побітова обробка у системах числення золотої пропорції 36

1.6 Вибір напрямку і формулювання задач досліджень. 421.    Вперше запропоновано теоретичні положення, що узагальнили системи числення як з цілою, так і з нецілою основою, придатні для порозрядного потокового виконання всіх арифметичних операцій (АМ-системи числення). Це дозволило порівнювати дані системи числення за витратами обладнання при побудові потокових засобів повнофункціональної побітової арифметики на їх основі. Проведений порівняльний аналіз АМ-систем числення показав, що найменші витрати обладнання при реалізації повнофункціональної побітової потокової обробки забезпечує використання системи числення золотої 1-пропорції. Дана система числення вибрана для реалізації методів і засобів повнофункціональної побітової арифметики;

2.    Удосконалено потоковий метод побітового додавання кодів золотої 1‑пропорції з урахуванням знаків, який відрізняється тим, що в ньому використовуються довільні форми прямих кодів зі знаками, розташованими після старших одиниць. Крім того, до появи обох знаків операндів встановлюється розгортання старшого розряду проміжного результату, яке забороняється після надходження їх останніх розрядів. Це забезпечило зменшення витрат обладнання при побудові пристроїв на основі даного методу, не потребуючи додаткових тактів між послідовними кодами;

3.    Удосконалено потоковий метод побітового множення кодів золотої 1‑пропорції, який відрізняється тим, що в ньому за допомогою декількох послідовностей тривходових побітових потокових суматорів додаються всі часткові добутки, сформовані у пари послідовних кодів. Це дозволило отримати незалежну від розрядності затримку потоку кодів добутків відносно потоку кодів операндів, не потребуючи додаткових тактів між послідовними кодами, та забезпечило лінійне зростання витрат обладнання при нарощуванні розрядності пристроїв, побудованих на основі даного методу;

4.    Удосконалено потоковий метод побітового ділення кодів золотої 1‑пропорції. Метод відрізняється тим, що на кожному етапі у другому такті після надходження старшої цифри дільника за допомогою додаткового аналізу його наступного розряду визначається черговий розряд частки, який вставляється у попередній код частки. Це забезпечило лінійне зростання витрат обладнання при нарощуванні розрядності пристроїв, побудованих на основі даного методу, не потребуючи додаткових тактів між послідовними кодами.

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

Виконані розробки рекомендацій щодо побудови пристроїв дозволили отримати такі практичні результати:

1.    Запропоновано рекомендації щодо побудови потокових пристроїв  зі зменшеними витратами обладнання для побітового додавання, віднімання, а також додавання з урахуванням знаків чисел, поданих прямими послідовними кодами золотої 1-пропорції у довільній формі. Використання довільних форм прямих кодів дозволило зменшити витрати обладнання при побудові пристроїв додавання і віднімання з урахуванням знаків відносно відомого побітового додавання і віднімання доповняльних кодів. При розрядності операндів 8 витрати обладнання зменшуються у 1,54 рази., а при розрядності 32 – у 4,17 рази;

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

3.    Як приклад використання розроблених засобів побітової потокової арифметики при подані інформації у форматі з фіксованою крапкою автором вперше запропоновано метод та рекомендації щодо побудови пристрою обчислення похибок лінійності передатної характеристики АЦП на основі побітової потокової обробки у системі числення золотої 1-пропорції, що дозволило виконувати самокалібрування його лінійності у процесі роботи.

З метою підтвердження результатів досліджень були виготовлені та пройшли випробування дослідні макети цифрового фібоначчієвого фільтра (ЦФФ) та фібоначчієвого послідовного арифметичного пристрою (ФПАП). Крім того, було проведене програмне моделювання розроблених пристроїв і алгоритмів. Результати дисертаційної роботи були впроваджені у Російському НДІ космічного приладобудування (м. Москва) та Інституті електроніки і зв’язку Української академії наук (м. Київ), що підтверджено відповідними актами, наведеними у додатку А.

1.            Июльская жара, «тирания соединений» и интегральная схема [Електронний ресурс] // VIOL: История радио: На пути к современному радио – Режим доступу до мат. :

http://files.radioscanner.ru/files/download/file2456/istoria_radio_v_imenah.pdf.

2.            Бабкин В. И. О перспективности организации российско-германской инвестиционной программы в области микроэлектроники [Електронний ресурс] / В. И. Бабкин. // Аналитические обзоры – Режим доступу до мат. :

http://www.sciteclibrary.ru/rus/catalog/pages/7717.html.

3.            Interconnect Technology, IEEE International Conference [Електронний ресурс] // IEEE Xplore : Digital library : Browse : Conferences – Режим доступу до мат. : http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000400.

4.            Яковлев Ю. С. Однокристальные компьютерные системы высокой производительности. Особенности архитектурно-структурной организации и внутренних процессов : монография / Яковлев Ю. С. – Винница : ВНТУ, 2009. – 294 с.

5.            SoC interconnect crisis: Path delays cancel speed increase [Електронний ресурс] / Chappell Brown, // EE Times. – Jun. 2003. ­– Режим доступу до мат. :

http://www.eetimes.com/story/OEG20030620S0028.

6.            The Future of Interconnects: How Will Billions of Transistors Communicate in the Nanometer Era [Електронний ресурс] / Nagaraj NS - Texas Instruments Inc., Dallas, TX // 44th Design Automation Conference San Diego. – Jun. 2007. – Режим доступу до мат. :

http://dl.acm.org/citation.cfm?id=1278623&dl=ACM&coll=DL&CFID=141366031&CFTOKEN=39676461.

7.            Wilson R. Industry takes aim at 22nm interconnect stack [Електронний ресурс] / R.Wilson // EDN network: electronics news – Режим доступу до мат. : http://www.edn.com/electronics‑news/4314122/Industry‑takes‑aim‑at‑22‑nm‑interconnect-stack.

8.            Данилина Г. IBM переводит закон Гордона Мура в третье измерение [Електронний ресурс] / Г. Данилина. // Наука и образование – Режим доступу до мат. : http://technomag.edu.ru/doc/71226.html.

9.            Будик А. IBM пронзила чипы водяными капиллярами [Електронний ресурс] / А. Будик. // 3D news: Новости Hardware – Режим доступу до мат. : http://www.3dnews.ru/news/ibm_osnastila_chipi_vodyanimi_kapillyarami/.

10.       Novikov A. Применение наноструктурированных материалов в технологии соединений [Електронний ресурс] / A. Novikov. // Abercate consulting: Аналитика – Режим доступу до мат. :

http://www.abercade.ru/research/analysis/1134.html.

11.       Свиденко Ю. 1 ГГц интегральная схема с межсоединениями из углеродных нанотрубок [Електронний ресурс] / Ю. Свиденко. // Nano News Net: Главная: Новости – Режим доступу до мат. :

http://www.nanonewsnet.ru/news/2008/1‑ggts‑integralnaya‑skhema‑s‑mezhsoedineniyami-iz-uglerodnykh-nanotrubok/.

12.       Медведев А. И. Технологическое обеспечение надежности межсоединений [Электронный ресурс] / А. И. Медведев. // Технология электронной промышленности. – 2005. – № 5 – Режим доступу до мат. :

http://www.tech-e.ru/pdf/2005_05_60.pdf.

13.       Ахманов А. С. Оптическая передача информации в супер­ЭВМ и микропроцессорных системах [Електронний ресурс] / А. С. Ахманов, О. Е. Наний, В. Я. Панченко. // Lightwave Russian Edition. – 2008. – № 3. – Режим доступу до мат. : http://photonics.net.ua/files/LRE/2008_No_3.pdf.

14.       Mikami Osamu, Uchida Teiji "Opto-Electronics Packaging Technology, Present Status and Prospect," Review of Laser Engineering Journal, – 2000. – Vol. 30., No. 10. – P. 571-575.

15.       Goodman, J. W. Optical interconnections for VLSI systems [Електронний ресурс] / J. W. Goodman, F. J. Leonberger, S.-Y. Kung, R. A. Athale // IEEE, Proceedings (ISSN 0018-9219). – Jul. 1984. – vol. 72. – P. 850–866. – Режим доступу до мат. : http://adsabs.harvard.edu/abs/1984IEEEP..72..850G.

16.       Lacy S. W. The Offset Cube: A Three-Dimensional Multicomputer Network Topology Using Through-Wafer Optics [Електронний документ] / W. S. Lacy, J. L. Cruz–Rivera, D. S. Wills // IEEE Transactions on Parallel and Distributed Systems. – Sept. 1998. – Vol. 9. – Is. 9. – P. 893–908. – Режим доступу до мат. :

http://www2.computer.org/portal/web/csdl/doi/10.1109/71.722222.

17.       Facanga H. S. Design of freshel holograms for optical interconnection of VLSI [Електронний документ] / H. S. Facanga, D. R. Selviah, K. Steptoe, M. Zhi-Qiang // Second International Conference on Holographic Systems, Components and Applications. IEEE, London, UK. – 1989. – P. 213–217. – Режим доступу до мат. : http://eprints.ucl.ac.uk/2671/1/2671.pdf.

18.       Chou J. Robust free space board-to-board optical interconnect with closed loop MEMS tracking [Електронний документ] / J. Chou, K. Yu, D. Horsley, B. Yoxall, S. Mathai, M. R. T. Tan, S.-Y. Wang, M. C. Wu // Applied Physics A: Materials Science & Processing. – Jun. 2009. – Vol. 95. – No 4. – P. 973–982. – Режим доступу до мат. :

http://www.springerlink.com/content/5u811h05gjk72u76/.

19.       Kang M. Floating dielectric slab optical interconnection between metal-dielectric interface surface plasmon polariton waveguides [Електронний документ] / M. Kang, J. Park, I.-M. Lee, B. Lee // Optics Express. – Jan. 2009. –Vol. 17. – Is. 2. – P. 676–687. – Режим доступу до мат. :

http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-17-2-676.

20.       Харьковский А. Оптический коммутатор IBM для применения в процессорах. [Електронний ресурс] / Александр Харьковский // 3DNews : Новости Hardware – Режим доступу до мат. :

http://www.3dnews.ru/news/opticheskii_kommutator_ibm_dlya_primeneniya_v_protsessorah/.

21.       G. Overton. Photonics applied: Can optical integration solve the computational bottleneck? [Електронний ресурс] – Режим доступу до мат. : http://www.laserfocusworld.com/articles/2009/03/photonics‑applied‑integrated‑photonics-can-optical-integration-solve-the-computational-bottleneck.html.

22.       Venditti M. B. Design and test of an optoelectronic VLSI chip with 40 element receiver trans mitter arrays using differential optical signaling / M. B. Venditti, E. Laprise, J. Faucher et al. // IEEE J. Select. Topics Quantum Electron. – 2003. – Vol. 9. – No. 2. – P. 361.

23.       Geib K. M. Fabrication and performance of two dimensional matrix addressable arrays of integrated vertical-cavity lasers and resonant cavity photodetectors / K. M. Geib, K. D. Choquette, D. K. Serkland et al. // IEEE J. Select. Topics Quantum Electron. – 2002. – Vol. 8. – P. 943.

24.       Hariyama M. A Field-Programmable VLSI Based on an Asynchronous Bit‑Serial Architecture / M. Hariyama, S. Ishihara, C. Wei, M. Kameyama // In: IEEE, Asian Solid-State Circuits Conference / Jeju, Korea. – Nov. 2007. – P. 380–383.

25.       Rettberg A. A Fully Self-Timed Bit-Serial Pipeline Architecture for Embedded Systems [Електронний ресурс] / A. Rettberg, M. Zanella, C. Bobda, T. Lehmann ­// – 2003. – Режим доступу до мат. :

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.3923.

26.       Andraka R. J. Building a high performance bit-serial processor in an FPGA / R. J. Andraka // Design SuperCom: Andraka consulting group: On-chip system design conference. – 1996.

27.       Ferguson L. FPGA-based FIR Filter Using Bit-Serial Digital Signal Processing [Електронний ресурс] / Lee Ferguson // – 2000. – Режим доступу до мат. : http://www.atmel.com/dyn/resources/prod_documents/DOC0529.PDF.

28.       Andraka R. J. FIR Filter Fits in an FPGA using a Bit Serial Approach [Електронний ресурс] / Raymond J. Andraka // – 2007. – Режим доступу до мат. : http://www.andraka.com/files/fir.pdf.

29.       Longa P. Area-Efficient FIR Filter Design on FPGAs using Distributed Arithmetic [Електронний ресурс] / P. Longa, A. Miri // – 2006. – Режим доступу до мат. :

http://www.computer.org/portal/web/csdl/doi/10.1109/ISSPIT.2006.270806.

30.       Fabris E. E. A bit-serial FFT processor [Електронний ресурс] / E. E. Fabris, G. A. Hoffmann, A. Susin, L. Carro // – 2001. – Режим доступу до мат. :

http://iie.fing.edu.uy/investigacion/grupos/microele//iberchip/pdf/50.pdf.

31.       David Crook, John Fulcher, "A Comparison of Bit Serial and Bit Parallel DCT Designs," VLSI Design. – 1995. – Vol. 3. – No. 1. – P. 59–65.

32.       Tsuyoshi Isshiki. "High-Performance Bit-Serial Datapath Implementation for Large-Scale Configurable Systems." PhD thesis, University of California at Santa Cruz, USA, 1996.

33.       Cyca D. Bit-Serial Digital Filter Implementation using a Custom C Compiler [Електронний ресурс] / D. Cyca, L.E. Turner // – 2007. – Режим доступу до мат. : http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4145449.

34.       Turner L. E. Bit-serial FIR Filters with CSD Coefficients for FPGAs [Електронний ресурс] / L. E. Turner, P. J. W. Graumann, S. G. Gibb // – 2007. – Режим доступу до мат. :

http://www.springerlink.com/content/y15j4101w4281441/fulltext.pdf?page=1.

35.       Weber R. Implementation of the AES Algorithm for a Reconfigurable Bit Serial, Fully Pipelined Architecture [Електронний ресурс] / R. Weber, A. Rettberg // – 2009. – Режим доступу до мат. :

http://www.springerlink.com/content/x488826185315065/.

36.       Rettberg A. Towards a High-Level Synthesis of Reconfigurable Bit-Serial Architectures [Електронний ресурс] / A. Rettberg, F. Dittmann, M. Zanella, T. Lehmann // – 2003. – Режим доступу до мат. :

http://www2.computer.org/portal/web/csdl/abs/proceedings/sbcci/2003/2009/00/20090079abs.htm.

37.       Dittmann F. Path Concepts for a Reconfigurable Bit-Serial Synchronous Architecture [Електронний ресурс] / F. Dittmann, A. Rettberg, R. Weber // – 2005. – Режим доступу до мат. :

http://www.springerlink.com/content/y5kk543864352395/fulltext.pdf?page=1.

38.       Visavakul C. A Digit-Serial Structure for Reconfigurable Multipliers [Електронний ресурс] / C. Visavakul, P. Y. K. Cheung, and W. Luk // – 2002. – Режим доступу до мат. : http://www.doc.ic.ac.uk/rr2001/luk.pdf.

39.       Ban T. Development of Digit-serial Floating Point Units for Scientific Computation Engine [Електронний ресурс] / T. Ban, Y. Shiraishi, K. Tanigawa, T. Hironaka // – 2008. – Режим доступу до мат. :

http://www.ieice.org/ken/paper/20080926oa5f/eng/.

40.       Wu X. One-bit processing for real-time control [Електронний ресурс] / X. Wu, R. Goodall // – 2003. – Режим доступу до мат. :

http://www.nt.ntnu.no/users/skoge/prost/proceedings/ecc03/pdfs/563.pdf.

41.       Свидиненко Ю. Клеточные автоматы на квантовых точках : Nanotechnology News Networc [Електронний ресурс] / Ю. Свидиненко // – 2006 – Режим доступу до мат. : http://old.nanonewsnet.ru/index.php?module= Pagesetter&func=viewpub&tid=9&pid=93.

42.       I. Amlani, A. O. Orlov, G. Toth, G. H. Bernstein, C. S. Lent, G. L. Snider "Digital Logic Gate Using Quantum-Dot Cellular Automata," SCIENCE. – Vol. 284. – Apr. 1999. – P. 289–291.

43.       Vetteth A. Quantum-dot cellular automata of flip-flops [Електронний ресурс] / A. Vetteth, K. Walus, V. S. Dimitrov, G. A. Jullien // The national Conference on Communications. – 2003. – Режим доступу до мат. :

www.ncc.org.in/download.php?f=NCC2003/L-6.pdf.

44.       Niemier M. Dataflow in molecular QCA: Logic can "sprint", but the memory wall can still be a "hurdle" [Електронний ресурс] / M. Niemier, P. Kogge, R. Murphy, A. Rodrigues, T. Dysart, and S. Frost // University of Notre Dam, Department of Computer Science and Engineering. – 2006. – Режим доступу до мат. : http://www.cse.nd.edu/Reports/2006/TR-2006-14.pdf.

45.       K. Walus, G.A. Jullien, and V.S. Dimitrov, "Computer Arithmetic Structures for Quantum Cellular Automata," Proc. Conf. Record of the 37th Asilomar Conf. Signals, Systems, and Computers. – 2003. – Vol. 2. – P. 1435­–1439.

46.       Timler, J., Lent, C.S., "Power gain and dissipation in quantum-dot cellular automata," J. Appl. Phys., American Institute of Physics. – 2002. – No 91 (2). – P. 823.

47.       Bit-Serial Adder Based on Quantum Dots : Tech briefs / Electronics & computers [Електронний ресурс] // NASA's Jet Propulsion Labaratory, Pasadena, California – 2003 – Режим доступу до мат. : 

http://www.techbriefs.com/component/content/article/911.

48.       W. J. Townsend, J. A. Abraham, "Complex Gate Implementations for Quantum Dot Cellular Automata ," 4th IEEE Conference on Nanotechnology. – Munich, Germany, 2004. – August 17–19. – P. 625–627.

49.       Свидиненко Ю. Одноатомная квантовая точка приближает эру квантовых компьютеров [Електронний ресурс] // Ю. Свидиненко – 2009. – Режим доступу до мат. :

http://www.nanonewsnet.ru/news/2009/odnoatomnaya-kvantovaya-tochka-priblizhaet-eru-kvantovykh-kompyuterov.

50.       V. K. Kornev, I. I. Soloviev and O. A. Mukhanov, "Possible Approach to the Driver Design Based on Series SQIF," IEEE Transaction on Applied Superconductivity. – 2005. – Vol. 15. – P. 388–391.

51.       Dmitry Zinoviev High-speed rapid single flux quantum (RSFQ). [Електронний ресурс] – Режим доступу до мат. :

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.6337.

52.       M. Tanaka, K. Obata, K. Takagi, N. Takagi, A. Fujimaki, N. Yoshikawa "A High-Throughput Single-Flux-Quantum Floating-Point Serial Divider Using the Signed-Digit Representation," IEEE Transactions on Applied Superconductivity. – 2009. – Vol. 19. – P. 653–656.

53.       Приборы на основе сверхпроводимости [Електронний ресурс] – 2009. – Режим доступу до мат. : http://radiomaster.ru/articles/view/587/.

54.       Зиновьев Д. Леденящая альтернатива [Електронний ресурс] / Д. Зиновьев // – 1999. – Режим доступу до мат. :

http://cs.mipt.ru/docs/comp/rus/hardware/other/altern/index.html.

55.       H. Park, Y. Yamanashi, K. Taketomi, N. Yoshikawa, A. Fujimaki, N. Takagi, "Novel serial-parallel converter using SFQ logic circuits," Physica C. – Sep. 2008. – Vol. 468. – P. 1977–1982.

56.       M. Ito, K. Kawasaki, N. Yoshikawa, A. Fujimaki, H. Terai, S. Yorozu, "20 GHz operation of bit-serial handshaking systems using asynchronous SFQ logic circuits," IEEE Transactions on Applied Superconductivity. – Jun. 2005. – Vol. 15. ­– P. 255–258.

57.       K. Kawasaki, K. Yoda, N. Yoshikawa, A. Fujimaki, H. Terai, S. Yorozu, "Design and implementation of a high-speed bit-serial SFQ adder based on the binary decision diagram," Supercond. Sci. Technol. – 2003. – Vol.16. – No. 12. – P. 1497–1502.

58.       H. Park, Y. Yamanashi, K. Taketomi, N. Yoshikawa, M. Tanaka, K. Obata, Y. Ito, A. Fujimaki, N. Takagi, K. Takagi, S. Nagasawa, "Design, Implementation, and On-Chip High-Speed Test of an SFQ Half-Precision Floating-Point Adder," IEEE Transaction on Applied Superconductivity. – Jun. 2009. – Vol. 19. – P. 634–639.

59.       H. Hara, K. Obata, H. Park,Y. Yamanashi,K. Taketomi, N. Yoshikawa, M.