nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 13 Dec 2018 21:21



Reply to topic  [ 41 posts ]  Go to page 1, 2, 3  Next
[Ternary] Tunguska II 
Author Message
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
Figured it would be a good idea to start a separate thread for discussion of the Tunguska rewrite I'm working on.

From the big Tunguska thread: I'm seriously considering a major overhaul of the core code of Tunguska. It would be largely backwards-compatible with current Tunguska assembly code (and thus also 3CC code), but use 9 digits per word instead of 6, and add more instructions and address modes.

There are fundamental problems with Tunguska as it is right now. Most of them stem from how it was written completely ad-hoc, with no real aim or sense of direction. It is therefore poorly modularized, impossible to fork, really difficult to modify, etc. It superficially looks somewhat neat, but it really is quite a mess.




Some specifics: It will be written in C99 instead of C++, and will be much better modularized. It will be possible to take the mathematics part and use it in other code without modification (it has as few as possible assumptions hard-coded, so you can for example change the number of digits by changing a single value), and adapting the code to write other machines will be much simpler.

Since Tunguska II will use 9 digits per word, it can address much more memory (~20,000 pages x 20,000 addresses, yielding a maximum of ~400,000,000 addressable words, Tunguska I can address 500,000 words for comparison).

Therefore, memory will be allocated when it is necessary on a page-by-page basis, instead of allocating the whopping 12 Gb native memory required in one go, since almost no computer has that much memory to work with. Some sort of safeguard against a fandangoing instruction pointer will also be necessary.

Status:
* The mathematics module is mostly done, it's got some fine-tuning to be done, but it works and does what it should.
* Most instruction-code is written, but they are yet to be tested thoroughly.
* Addressing modes are implemented, but probably buggy.

Stuff to be done:
* I/O is not implemented.
* Interrupts are not implemented.
* The assembler has not been adapted to also produce Tunguska II code.


As stated previously, Tunguska II will support all Tunguska I instructions, but also add new instructions and addressing modes (a lot like Intel does when it comes up with new processors). It will not be binary compatible, but porting code should be pretty simple.

I haven't decided yet exactly what to add (suggestions are welcome), but so far I'm leaning towards a couple of new general purpose registers.


17 Jun 2009 17:33
Profile
Retired

Joined: 03 Aug 2003 23:37
Posts: 1481
Location: Moscow
Reply with quote
Thanks! Good news. Any help I can provide?


18 Jun 2009 06:42
Profile
Reply with quote
I have a question:

A lot of effort is put in preparing the Tunguska, I want to know how can it be made useful for developing applications over it?

Also is it possible to have Tundusaka II modules made/designed using XML or JSON, that way it will become cross platform, even we will be able to use it over Internet, as most of people do not download and Install the software, for them it will be an option.

All that is just suggestion.


18 Jun 2009 11:28
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
Speed is a major issue with those technologies. It's pretty important for a program like Tunguska to run fast, which typically requires host-optimized code.

It might be possible to port it to Java, though, since it can at times be pretty fast. I'll port the mathematics module of Tunguska II to Java and see how fast it runs, and if it runs fast enough, I'll consider parallel development of both a C and a Java runtime. (With java you have dynamic class loading and all sorts of fun stuff to play with)


18 Jun 2009 12:03
Profile
Reply with quote
That sounds Great!!!

I am in, allow me to help in Java Converions and Java GUIs.


18 Jun 2009 12:57
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
I've ported the mathematics code I've written in C to Java. I haven't tested it very thoroughly, though. But superficially it seems to work for the most part. I'm gonna do some speed tests later.

Code:
/* Balanced ternary arithmetics library.
 *
 *
 *
 *
 */

package tunguska.balanced;

/**
 *
 * @author Viktor Lofgren
 * @version Test-1
 */
public class Word {

    /** Number of digits of word */
    public static final int DIGITS = 9;

    /** 3<sup>DIGITS</sup> (Maximum value of equivalent
     * non-balanced ternary form) */
    public static final int NB_MAX = 19383;

    /** Maxiumum value */
    public static final int MAX = NB_MAX/2;

    /** Minimum value */
    public static final int MIN = -MAX;

    int[] digits;

    /** Benchmark test
     *
     */
    public static void test() {


    }

    public Word() {
        digits = new int[DIGITS];
    }

    /** Performs a series of loans and carries to make sure
     * that a malformed word (e.g. [1,1,2]) is turned into a proper
     * ternary word (in this case [1, -1, -1, -1])
     *
     * @return carry
     */
    int ripple() {
          int carry = 0;
          for(int i = 0; i < DIGITS; i++) {
              digits[i] += carry;
             
              if(digits[i] > 0) {
                  carry = (digits[i] + 1) / 3;
              } else {
                  carry = (digits[i] - 1) / 3;
              }

              digits[i] -= 3*carry;
          }
         
          return carry;
    }

    int ripple1() {
        int carry = 0;
          for(int i = 0; i < DIGITS; i++) {
              digits[i] += carry;

              if(digits[i] > 0) {
                  carry = (digits[i] + 1) / 3;
              } else {
                  carry = (digits[i] - 1) / 3;
              }

              if(carry == 0) return 0;

              digits[i] -= 3*carry;
          }

          return carry;
    }

    public int[] getDigits() { return digits; }

    /** Copy the digits of a word to this word */
    public void copy(Word w) {
        for(int i = 0; i < DIGITS; i++ )
            digits[i] = w.getDigits()[i];
    }

    /** Clear all digits (effectively setting the word = 0)*/
    public void zero() {
        for(int i = 0; i < DIGITS; i++)
            digits[i] = 0;
    }

    /** Populate digit array with values equivalent to the given integer value.
     * Wrap-around if |i|>MAX
     */
    public void fromInteger(int i) {
        if(i == 0) { for(int j = 0; j < DIGITS; j++) digits[j] = 0; }
        else for(int j = 0; j < DIGITS; j++) {
            if(i < 0) {
                digits[j] = i - 3 * ((i - 1) / 3);
            } else {
                digits[j] = i - 3 * ((i + 1) / 3);
            }
            i = (i - digits[j]) / 3;
        }
    }

    /** Increment word by integer value i */
    public int addInteger(int i) {
        digits[0] += i;
        return ripple1();
    }


    /** Calculate equivalent value in host integer form */
    public final int integerValue() {
        int sum = 0;
        for(int i = DIGITS-1; i >= 0; --i) {
            sum = sum * 3 + digits[i];
        }

        return sum;
    }

    /** Return sgn(this - w) */
    public int compare(Word w) {
        int[] wDigits = w.getDigits();
        for(int i = DIGITS-1; i >= 0; --i) {
            if(digits[i] > wDigits[i]) return 1;
            else if(digits[i] < wDigits[i]) return -1;
        }
        return 0;
    }

    /** Return most significant digit */
    public int mostSignificant() {
        for(int i = DIGITS-1; i >= 0; --i) {
            if(digits[i] != 0) return digits[i];
        }

        return 0;
    }

    /** Calculate the sum of two words, put the result in a third word
     *
     * @return carry
     */
    public static int sum(Word target, Word a, Word b) {
        int carry = 0;
        int[] tdigits = target.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();
       
        for(int i = 0; i < DIGITS; i++) {
            tdigits[i] = carry + adigits[i] + bdigits[i];

            if(tdigits[i] > 0)
                carry = (tdigits[i] + 1) / 3;
            else
                carry = (tdigits[i] - 1) / 3;

            tdigits[i] -= 3*carry;
        }

        return carry;
    }

    /** Calculate the difference between two words, put the
     * result in a third word.
     *
     * @return carry
     */
    public static int diff(Word target, Word a, Word b) {
        int carry = 0;
        int[] tdigits = target.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            tdigits[i] = carry + adigits[i] - bdigits[i];

            if(tdigits[i] > 0)
                carry = (tdigits[i] + 1) / 3;
            else
                carry = (tdigits[i] - 1) / 3;

            tdigits[i] -= 3*carry;
        }

        return carry;
    }

    /** Add another word onto this word
     * @return carry
     */
    public int add(Word w) {
        int carry = 0;

        int[] wdigits = w.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            digits[i] = carry + digits[i] + wdigits[i];

            if(digits[i] > 0)
                carry = (digits[i] + 1) / 3;
            else
                carry = (digits[i] - 1) / 3;

            digits[i] -= 3*carry;
        }

        return carry;
    }

   /** Subtract another word from this word
    * @return carry
    */
    public int sub(Word w) {
        int carry = 0;

        int[] wdigits = w.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            digits[i] = carry + digits[i] - wdigits[i];

            if(digits[i] > 0)
                carry = (digits[i] + 1) / 3;
            else
                carry = (digits[i] - 1) / 3;

            digits[i] -= 3*carry;
        }

        return carry;
    }

    /** Multiply two words.
     * @param target_high  High digits (may be set to null)
     * @param target_low Low digits
     * @param a  First word to be multiplied
     * @param b  Second word to be multiplied
      */
    public static void mul(Word target_high, Word target_low,
                    Word a, Word b) {
        target_low.zero();
        int[] tldigits = target_low.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            if(adigits[i] != 0) for(int j = 0; j < DIGITS - i; j++) {
                tldigits[i+j] += adigits[i] * bdigits[j];
            }
        }

        int carry = target_low.ripple();
        if(target_high != null) {
            target_high.zero();
            int[] thdigits = target_high.getDigits();

            thdigits[0] = carry;
            for(int i = 1; i < DIGITS; i++) {
                if(adigits[i] != 0) for(int j = DIGITS- i; j < DIGITS; j++) {
                    thdigits[i+j-DIGITS] += adigits[i] * bdigits[j];
                }
            }
        }

    }

    /** Divide two numbers
     *
     * @param remainder dividend modulo divisor (may be set to null)
     * @param quotient dividend / divisor (may be set to null)
     */
    public static void divide(Word quotient, Word remainder,
                    Word divisor, Word dividend) {
        int dr = divisor.integerValue();
        int dd = dividend.integerValue();

        /* FIXME: Deal with division by zero */
        if(dd == 0) {
            dd = 1;
        }

        if(quotient != null) quotient.fromInteger(dd/dr);
        if(remainder != null) remainder.fromInteger(dd/dr);
       
       
    };

    /** Multiply all digits by -1 */
   
    public void invert() {
        for(int i = 0; i < DIGITS; i++) {
            digits[i] *= -1;
        }
    };

    /** Shift all digits to the left */
    public void shiftLeft(int amount) {
        int i;
        for(i = 0; i < DIGITS-amount; i++)
            digits[i] = digits[i+amount];
       
        for(; i < DIGITS; i++)
            digits[i] = 0;
       
    }

    /** Shift all digits to the right */
    public void shiftRight(int amount) {
        for(int i = 0; i < DIGITS - amount; i++)
            digits[i+amount] = digits[i];

        for(int i = 0; i < amount; i++)
            digits[i] = 0;
    };
}


18 Jun 2009 13:37
Profile
Reply with quote
It appears that you have optimized your code alot, you have kept the complexity to "n", Great Job!!!

so this is the complete Mathematics Module ?


18 Jun 2009 14:13
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
I'm happy with the complexity of the functions, especially addInteger which has a worst-case complexity of O(n)

This is most of the module. It needs some minor fine-tuning. I'm also working on the logic code.

I did some preliminary benchmarking:

Code:
        Word a = new Word();
        Word b = new Word();
        Word prod = new Word();
        for(int i = MIN; i <= MAX; i++) {
            for(int j = MIN; j <= MAX; j++) {
                a.fromInteger(i);
                b.fromInteger(j);
                Word.mul(null, prod, a, b);
            }
        }

runs in 2 minutes 37 seconds (that is pretty good, since multiplication is a very slow operation, and it's doing it 3^18 times).

Code:
        word a, b, prod;
        int i, j;
        for(i = WORD_MIN; i <= WORD_MAX; i++) {
                for(i = WORD_MIN; i <= WORD_MAX; i++) {
                        bw_from_i(a, i);
                        bw_from_i(b, j);
                        bw_mul(NULL, prod, a, b)
                }
        }


Heavily optimized C code runs in (-O3): 3 minutes 45 seconds! This wasn't a very controlled experiment, but it certainly bodes well for the possibility of a full Tunguska port.


18 Jun 2009 14:43
Profile
Reply with quote
Hi,

I am not sure of these complexities but complexity in "minutes", I think should be brought down to milliSeconds.

I had code written for addition and multiplications (for TVM),but it was just milliseconds operation for me, however it was rule based and not exactly a mathematical function.

I hope this comes down to seconds.


18 Jun 2009 16:13
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
It's running the multiplication operation 387,420,489 times for all possible values (you get a better statistical sample that way.) and that's why it takes minutes.

The time for a single loop iteration is:
0.4 microseconds for Java
0.6 microseconds for C.

The time for just the multiplication is about half that value.

This is really good. Comparing these results with calculations done with host arithmetic, it runs about 1% the speed of native mathematics (and if you consider all the "cheating" processors do with pipe lining and stuff, it's even better). It's running around the same speed as a Pentium 1.


18 Jun 2009 16:23
Profile
Reply with quote
True, its really good and looks great!!!

I was in confusion that it takes so much time runnig the calculation, but now its Clear.

So, does Java performs better? with your algorithm, thats something unexpected.


18 Jun 2009 18:53
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
Java performance really depends a lot on the programmer. If it is written in a smart way, it can certainly out-perform C (since it's easier to optimize code that doesn't have pointers). From how I understand it, the performance loss from being an interpreted language pretty much goes away with JIT-compilation.

It is also easy to write code that is very slow in Java if you don't think about what you're doing.

Anyway, I've done some preliminary work on the architecture of Tunguska. You can have look at the javadocs to get a feel for how it's structured, if you want.


18 Jun 2009 19:15
Profile
Reply with quote
Ya i got some picture in mind....let me know when start working on GUI for the same...i am excited to USE JavaFX for ternary.


18 Jun 2009 21:26
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
Did some major re-factoring of the code to make better use of the object orientation of Java. I've updated the javadocs (same location).

Most of the core implementation is more or less functional. I've got some preliminary benchmarks for you:

It runs 100 million instructions in 22 seconds (roughly 5 million instructions per second), same order of magnitude as an Intel 386 DX.

Tunguska does around 2 million instructions per second when you take away all the I/O, so considering that, things are looking promising :-)


19 Jun 2009 16:16
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 17214
Location: Colorado
Reply with quote
It sounds really strange for me that Java does mathematics faster than optimized C. Do you have multicore processor or something? Did you try "vectorization" options for GCC to compile your program?

P.S. Java version is good. It means it is possible to do Android version of Tunguska-II :)


19 Jun 2009 19:51
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 41 posts ]  Go to page 1, 2, 3  Next

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.