logo

SCIENTIA SINICA Informationis, Volume 51 , Issue 5 : 750(2021) https://doi.org/10.1360/SSI-2019-0240

Design and implementation of parallel MSD integer divider in ternary optical computer

More info
  • ReceivedOct 31, 2019
  • AcceptedDec 5, 2019
  • PublishedMar 30, 2021

Abstract


Funded by

安徽省教育厅自然科学基金重点项目(KJ2017A452)

上海市科研计划专项(15700500400)

国家自然科学基金面上项目(61073049)


References

[1] Obermann S F, Flynn M J. Division algorithms and implementations. IEEE Trans Comput, 1997, 46: 833-854 CrossRef Google Scholar

[2] Liu H P. Research on high-performance arithmetic for floating-point division and the elementary functions. Dissertation for Ph.D. Degree. Beijing: Institute of Computing Technology, Chinese Academy of Sciences, 2003. Google Scholar

[3] Hooman N. Architectures for floating-point division. Dissertation for Ph.D. Degree. Adelaide: Adelaide University of Australia, 2005. Google Scholar

[4] Atkins D E. The Theory and Implementation of SRT Division. Technical Report UIUCDCS-R-67-230, 1967. Google Scholar

[5] Tocher K D. TECHNIQUES OF MULTIPLICATION AND DIVISION FOR AUTOMATIC BINARY COMPUTERS. Q J Mech Appl Math, 1958, 11: 364-384 CrossRef Google Scholar

[6] Xu Q, Jin Y, Shen Y F, et al. MSD iterative division algorithm and implementation technique for a ternary optical computer. Sci China Inf Sci, 2016, 46: 539--550. Google Scholar

[7] Liu Ji. Design of divider in high performance CPU. Dissertation for Master's Degree. Tongji University, 2007. Google Scholar

[8] Yuan J H. Design and perforrmance improvement of high- perforrmance divider based on SRT algorithm. Dissertation for Master's Degree. Graduate School of National University of Defense Science and technology, 2015. Google Scholar

[9] Jiang J B, Zhang X F, Shen Y F, et al. Design and Implementation of SJ-MSD Adder in Ternary Optical Computer. Acta Electronica Sinica, C 180572. Google Scholar

[10] Jiang J B, Chen X L, Ouyang S. Hardware implementation of converting ternary optical computer MSD into standard binary data. J Nanjing Univ Sci Tech, 2016, 40: 278--284. Google Scholar

[11] Avizienis A. Signed-Digit Numbe Representations for Fast Parallel Arithmetic. IEEE Trans Electron Comput, 1961, EC-10: 389-400 CrossRef Google Scholar

[12] Yan J Y, Jin Y, Zuo K Z. Decrease-radix design principle for carrying/borrowing free multi-valued and application in ternary optical computer. Sci China Ser F-Inf Sci, 2008, 51: 1415-1426 CrossRef Google Scholar

  • Figure 1

    Execution flow chart of single data MSD integer division

  • Figure 2

    (Color online) Appearance of machine 1 of SD16

  • Figure 3

    Processor pixel arrangement and divider processor bit allocation

  • Table 1   SJ transformation — $S_1$, $S_2$, $J_1$, $J_2$ and $J_3$ ternary logic transformation
    Transformation $S_1$Transformation $S_2$Transformation $J_1$Transformation $J_2$Transformation $J_3$
    $b$$a$$b$$a$$s_1$$s_2$$s_1$$s_2$$j_2$$j_1$
    0 1 u 01u0 1 0101
    0 0 0 u 0 0 1 1 0 0 1 0 0 u 0 0 1
    1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0
    u u 0 u u 1 0 0 u 0 0 u u 0 u u 0
  • Table 2   Comparator truth table $C$
    $b$$a$
    01u
    0 0 1 u
    1 1 1 u
    u u 1 u
  • Table 3   Table of experiment cases
    Case Dividend 1 Divisor 1 Dividend 2 Divisor 2 Dividend 3 Divisor 3
    1 11u0uuuu01001uu1 11u1u1u0 $\phi$$\phi$$\phi$1uuuu011u0u10 uuuuu101 uuu11111u10u1u0u $\phi$$\phi$1101u1
    2 $\phi$u110u1u1u101u01 u0u11010 u011u0u100u010u0 1uu01001 1u1000u010u11u0u u0u1101u
    3 u0100u0101u0u1u0 1u10u0u0 1u001u0u00u010u1 u1u1u1u1 u1u01u0101110u1u u000u010
    4 u1u0101u10u1uu01 01101001 $\phi$$\phi$$\phi$$\phi$$\phi$$\phi$$\phi$$\phi$u010u1u0 u1uuu011 111u0u011u0u11uu 10u0u1uu
    5 1u10000uu0uu110u u1u1u10u u010000000001uu1 $\phi$11u0u10 $\phi$$\phi$1u0u0100001uu1 110u0u10
    6 $\phi$1uu01u100uu110u u101u0u1 u0100001uu101uu1 10u111u1 101001u001101uu1 u00u100u
    7 1u1u1010u110uu01 10u11010 1u0u100u0u0110u0 uu0u1001 1u1000u0100u0u01 1u1uuu1u
    8 $\phi$1u0u1u0100u01u0 1u0uu101 1u10u010u01u0u01 u1uu11u1 1u0101u1u0110u1u u0u00000
    9 0000000000000000 00000001 0000000000000001 00000001 000000000000000u 00000001
    100000000000000000 0000000u 0000000000000001 0000000u 000000000000000u 0000000u
    110000000000000000 11111111 0000000000000001 11111111 000000000000000u 11111111
    120000000000000000 uuuuuuuu 0000000000000001 uuuuuuuu 000000000000000u uuuuuuuu
    130000000000000000 00000001 1111111111111111 00000001 uuuuuuuuuuuuuuuu 00000001
    140000000000000000 0000000u 1111111111111111 0000000u uuuuuuuuuuuuuuuu 0000000u
    150000000000000000 11111111 1111111111111111 11111111 uuuuuuuuuuuuuuuu 11111111
    160000000000000000 uuuuuuuu 1111111111111111 uuuuuuuu uuuuuuuuuuuuuuuu uuuuuuuu
    171u10000uu0uu110u 00000000 u010000000001uu1 u11u0u10 1u1u0u0100001uu1 110u1010
    1801uu01u100uu110u u110u0u1 u0100001uu101uu1 00000000 101001u001101uu1 u00u110u
    191u1u1010u110uu01 10u1u110 1u0u100u0u0110u0 uu0u1101 1u1000u0100u0u01 00000000
  • Table 4   Record table of experimental results
    Case 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
    Result checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark checkmark
  • Table 5   Calculation results table of experimental cases
    Case Quotient 1 Remainder 1 Quotient 2 Remainder 2 Quotient 3 Remainder 3
    1 0000000011011010 0001u00000u1 000000000000001u 01u1uu00001u 000000uuuu00u0u0 0000000u01uu
    2 0000000000100011 00000u00u00u 000000u000u0uu00 0000000u1uu0 00000000u0uu00uu 0000001u00u0
    3 0000000u00u00uu0 000000u000u0 00000000uu00u00u 000001u1u010 0000000010101101 000000000u0u
    4 00000000uu0u00uu 000000u10000 0000000000000000 0000u010u1u0 0000001001001110 000000100u0u
    5 0000000u000uuu00 0000001u000u 0000000u00uuu0uu 000000000u1u 0000000000010011 00000010u01u
    6 000000000u0u0u00 000001u0100u 00000000uu000uuu 000000000000 0000000u00u0uuuu 00001u000u00
    7 0000000010111100 0001uu000u01 000000000u000uu0 0001u00u0u00 0000000101011110 0000001u10u1
    8 0000000010010110 000001u0uu00 00000000uuu000u0 0001u0u001u1 00000000u0000u00 0000010u0u1u
    9 0000000000000000 000000000000 0000000000000001 000000000000 000000000000000u 000000000000
    10 0000000000000000 000000000000 000000000000000u 000000000000 0000000000000001 000000000000
    11 0000000000000000 000000000000 0000000000000000 000000000001 0000000000000000 00000000000u
    12 0000000000000000 000000000000 0000000000000000 000000000001 0000000000000000 00000000000u
    13 0000000000000000 000000000000 1111111111111111 000000000000 uuuuuuuuuuuuuuuu 000000000000
    14 0000000000000000 000000000000 uuuuuuuuuuuuuuuu 000000000000 1111111111111111 000000000000
    15 0000000000000000 000000000000 0000000100000001 000000000000 0000000u0000000u 000000000000
    16 0000000000000000 000000000000 0000000u0000000u 000000000000 0000000100000001 000000000000
    17 Because the existing divisor is 0, division is terminated
    18 Because the existing divisor is 0, division is terminated
    19 Because the existing divisor is 0, division is terminated
qqqq

Contact and support