The variable bit cpu

[Skybuck Flying]

Hi,

I think I might have just invented the variable bit cpu

It works simply like this:

Each "data bit" has a "meta data bit".

The meta data bit describes if the bit is the ending bit of a possibly large
structure/field.

The meta bits together form a sort of bit mask or bit pattern.

For example the idea is best seen when putting the data bits
and meta bits below each other.

data bits: 01110101110101101010101
meta bits: 00000000100010001100001

In reality the data bit and meta bit are grouped together as a single entity
which can be read into the cpu since otherwise the cpu would not know where
to start reading the data or meta bits. Now it simplies start with the first
data + meta bit pair.

Because a cpu might need to know the length of the bit field up front the
cpu/algorithm works simply as follows:

The cpu starts reading data and meta bits until it reaches a meta bit of 1.

All bits that form the variable bit field are now read and can be used etc.

The above example then looks like this:

data bits: 011101011#1010#1101#0#10101
meta bits: 000000001#0001#0001#1#00001

(The # sign is too indicate to you where the variable bit fields are.)

Notice how even single bit fields are possible.

The reason for the variable bit cpu with variable bit software is too save
costs and to make computers/software even more powerfull and usefull

For example:

Currently fixed bitsoftware has to be re-written or modified, re-compiled,
re-documented, re-distributed, re-installed, re-configured when it's fixed
bit limit is reached and has to be increased for example from 32 bit to 64
bit etc.

Example are windows xp 32 to 64 bit, the internet IPv4 to IPv6.

Bye,
Skybuck.

 

[Harald]

Hi,

I think I might have just invented the variable bit cpu

Cool idea, not new and not exactly related to Java, because Java is
not too much concerned with the underlying CPU.

Harald.

 

[Skybuck Flying]

Cool idea, not new and not exactly related to Java, because Java is
not too much concerned with the underlying CPU.

Yes but java is fixed bit limited isn't it ?

Bye,
Skybuck.

 

[Roedy Green]

For example the idea is best seen when putting the data bits
and meta bits below each other.

data bits: 01110101110101101010101
meta bits: 00000000100010001100001

You had such architectures way back with IBM 1400 series and the
Burroughs 1700. The Burroughs was bit addressable. The IBM used
variable length number fields with field marks to delimit them.

--
Bush crime family lost/embezzled $3 trillion from Pentagon.
Complicit Bush-friendly media keeps mum. Rumsfeld confesses on video.
http://www.infowars.com/articles/us/mckinney_grills_rumsfeld.htm

Canadian Mind Products, Roedy Green.
See http://mindprod.com/iraq.html photos of Bush's war crimes

 

[Patricia Shanahan]

Hi,

I think I might have just invented the variable bit cpu

It works simply like this:

Each "data bit" has a "meta data bit".

The meta data bit describes if the bit is the ending bit of a possibly large
structure/field.

The meta bits together form a sort of bit mask or bit pattern.

For example the idea is best seen when putting the data bits
and meta bits below each other.

data bits: 01110101110101101010101
meta bits: 00000000100010001100001

This seems more like comp.arch material than language-related, but here
are a few random issues to think about:

I think you should consider more efficient encodings, so that less data
has to be moved around and stored in caches and registers. This one
takes 2n bits to store n payload bits. Have you thought about storing a
length prefix? The raw prefix takes only log_2(n) bits, and even with
encoding to distinguish the boundary between prefix and field should be
less than n bits for all except the shortest fields.

Incidentally, a processor with instructions for each power of two length
never takes more than 2(n-1) bits to store n payload bits. Maybe you
should be arguing for instructions that operate on 1, 2, and 4 bits?
Processors already support 8, 16, 32, and 64 bit operations.

How would fields be named in instructions? Bit addresses? Does the
processor ever have to scan earlier fields to find the one it is
supposed to be operating on?

Be careful with data that can cross boundaries, such as cache line and
page boundaries. You can end up with situations in which it is quite
difficult to get all the data for an instruction into the processor at
the same time, especially if you have a low associativity cache or page
translation table. I had problems making sure I always had enough free
pages when working on paging for a processor that used fields up to 256
bytes long, with the length in bytes encoded in the instruction.

I strongly recommend against unbounded fields lengths. That can force the
processor to be able to interrupt in the middle of executing an
instruction, and save a partially executed state. Very messy.

Patricia

 

[Patricia Shanahan]

Patricia Shanahan wrote:
....

Incidentally, a processor with instructions for each power of two length
never takes more than 2(n-1) bits to store n payload bits. Maybe you

This is correct only for n>1.

should be arguing for instructions that operate on 1, 2, and 4 bits?
Processors already support 8, 16, 32, and 64 bit operations.

....

 

[Skybuck Flying]

new encoding:

type field + type marker + length field + length maker + data

example:
1 bit + 1 bit + 20 bits + 20 bits + 1 milion bits.

The first 4 fields use the original encoding idea for flexibility's sake.

Since the length is now known the data does not need any markers.

The type field is to indicate the encoding method.

However suppose that computers could never address more than 80 bits...

Since some say 2^80 is the maximum number of atoms in the universe...

Maybe the encoding could simply be:

80 bits length field + data ?

Bye,
Skybuck.

 

[Tor Iver Wilhelmsen]

Yes but java is fixed bit limited isn't it ?

Sort of: There is always java.util.BitSet, but that will be a little
slower than using primitives directly.

 

[Tor Iver Wilhelmsen]

Yes but java is fixed bit limited isn't it ?

Sort of: There is always java.util.BitSet, but that will be a little
slower than using primitives directly.

 

[Patricia Shanahan]

At this point, I have no idea why building this into the CPU would be
any better than using software loops, such as for BigInteger.

With unbounded length, or very long lengths such as a million bits, the
processor would have to treat it as a loop, and stream data into and out
of its registers the way software would. Why would it be any better
built into the processor than done using software?

Patricia

 

[steve]

Hi,

I think I might have just invented the variable bit cpu

It works simply like this:

Each "data bit" has a "meta data bit".

The meta data bit describes if the bit is the ending bit of a possibly large
structure/field.

The meta bits together form a sort of bit mask or bit pattern.

For example the idea is best seen when putting the data bits
and meta bits below each other.

data bits: 01110101110101101010101
meta bits: 00000000100010001100001

In reality the data bit and meta bit are grouped together as a single entity
which can be read into the cpu since otherwise the cpu would not know where
to start reading the data or meta bits. Now it simplies start with the first
data + meta bit pair.

Because a cpu might need to know the length of the bit field up front the
cpu/algorithm works simply as follows:

The cpu starts reading data and meta bits until it reaches a meta bit of 1.

All bits that form the variable bit field are now read and can be used etc.

The above example then looks like this:

data bits: 011101011#1010#1101#0#10101
meta bits: 000000001#0001#0001#1#00001

(The # sign is too indicate to you where the variable bit fields are.)

Notice how even single bit fields are possible.

The reason for the variable bit cpu with variable bit software is too save
costs and to make computers/software even more powerfull and usefull

For example:

Currently fixed bitsoftware has to be re-written or modified, re-compiled,
re-documented, re-distributed, re-installed, re-configured when it's fixed
bit limit is reached and has to be increased for example from 32 bit to 64
bit etc.

Example are windows xp 32 to 64 bit, the internet IPv4 to IPv6.

Bye,
Skybuck.

congrats for re-inventing a suboptimal 200 year old idea.
read up on the history of computing.

 

[Skybuck Flying]

At this point, I have no idea why building this into the CPU would be
any better than using software loops, such as for BigInteger.

With unbounded length, or very long lengths such as a million bits, the
processor would have to treat it as a loop, and stream data into and out
of its registers the way software would. Why would it be any better
built into the processor than done using software?

I have no idea.. but maybe the cpu/hardware can have special hardware/logic
to speed it up...

Though just for kicks I think some day I will implement it in software

First have to flesh/design it out etc

Bye,
Skybuck

 

[Skybuck Flying]

congrats for re-inventing a suboptimal 200 year old idea.

read up on the history of computing.

Actually putting a mark/line under something is probably even older than 200
years

Though it seems nobody has ever thought of using a marker under bits like
this:

1101101
0000001 <- digital marker

Bye,
Skybuck.

 

[Patricia Shanahan]

I have no idea.. but maybe the cpu/hardware can have special hardware/logic
to speed it up...

For comparison, vector processors have similar issues. They used to get
big performance gains through special pipelining hardware, allowing
multiple data fetches, computations, and data stores to be going on at once.

They are largely obsolete, because a series of hardware and compiler
developments have let off-the-shelf processors do extremely well on
vectorizable loops. The extra complexity of a vector processor just
isn't worth it.

For your ideas to be taken seriously, you need to explain why putting
this in hardware brings a significant gain in the face of the last 25
years or so of processor and compiler developments.

Though just for kicks I think some day I will implement it in software

How is it better, as software, than all the other software implemented
variable length arithmetic types, including java.math.BigInteger?

 

[Tim Tyler]

[field terminators?]

Actually putting a mark/line under something is probably even older than 200
years

Though it seems nobody has ever thought of using a marker under bits like
this:

1101101
0000001 <- digital marker

Bit consicous folk often use things like Huffman coding instead
to store variable-length bit fields - since that is proven not
to waste space.

 

[Patricia Shanahan]

Actually putting a mark/line under something is probably even older than 200
years

Though it seems nobody has ever thought of using a marker under bits like
this:

1101101
0000001 <- digital marker

How do you know it hasn't been thought of before, but rapidly rejected,
without being published, for excessive inefficiency? N-1 zero bits
followed by a 1 is among the least efficient known representations of
the number N.

I'm not sure you are really thinking about this from the point of view
of a processor that has to store these things in registers, memories,
and caches, and use precious data path bandwidth to move them around.

If you have not studied modern cpu architecture much, I strongly
recommend "Computer Architecture: A Quantitative Approach" by John L.
Hennessy and David A. Patterson. I believe the 3rd edition is still current.

Patterson, with David Ditzel, was one of the authors of the 1980
Computer Architecture News article "The Case for the Reduced Instruction
Set Computer" that marked the start of the RISC revolution that has
dominated the last 25 years of processor design, and the book is written
from that perspective. Your variable length field proposal really steps
away from that, reintroducing ideas that fit more into the CISC theme.
However, I think you do need to explain why your proposal is any good in
terms of current computer architecture thought, and familiarity with the
ideas discussed in Hennessy and Patterson is essential to be able to do
that.

Patricia

 

[Skybuck Flying]

For comparison, vector processors have similar issues. They used to get
big performance gains through special pipelining hardware, allowing
multiple data fetches, computations, and data stores to be going on at

once.

Vector processors sound like graphics processors ?

They are largely obsolete, because a series of hardware and compiler
developments have let off-the-shelf processors do extremely well on
vectorizable loops. The extra complexity of a vector processor just
isn't worth it.

For your ideas to be taken seriously, you need to explain why putting
this in hardware brings a significant gain in the face of the last 25
years or so of processor and compiler developments.


How is it better, as software, than all the other software implemented
variable length arithmetic types, including java.math.BigInteger?

Ok, second time you asked this question so now I feel required to answer it


I have looked up this BigInteger thing... and as I suspected it uses java
byte arrays to initialize it. It also uses java integers to initialize it
etc.

Assuming that java integers are 32 bits and assusing byte array's are
limited to 2 GB (31 bits) or maybe 4 GB (32 bits) this would mean that
Java's Big Number is limited to 2 or 4 GB
at best.

Though looking at the api:

int bitCount()
int bitLength()
int getLowestSetBit()
flipBit(int n)

etc etc etc.

It seems to be limited to 2 Gigabit. That's exactly 256 MB ram.

One remaining question is, can these be serialized ? >- probably via byte
array's... but is the length stored somewhere as well ? probably... so that
would mean the length field is fixed as well etc...

So it is clear that BigNumber has it's limitations

Bye,
Skybuck.

 

[Skybuck Flying]

Sort of: There is always java.util.BitSet, but that will be a little
slower than using primitives directly.

BitSet(int nbits)
Creates a bit set whose initial size is large enough to explicitly
represent bits with indices in the range 0 through nbits-1.

Since it uses java integers which are probably 32 bits... This BitSet is
limited to 4 Gigabit
(256 MB).

Bye,
Skybuck.

 

[Skybuck Flying]

[field terminators?]

Actually putting a mark/line under something is probably even older than 200
years

Though it seems nobody has ever thought of using a marker under bits like
this:

1101101
0000001 <- digital marker

Bit consicous folk often use things like Huffman coding instead
to store variable-length bit fields - since that is proven not
to waste space.

Dynamic huffman is proven to waste space. It first needs every single
occurence to be transmitted into the tree.

So transmitting 256 bytes will always require 256 bytes. Plus even some more
overhead bits.

So for small bits of information dynamic huffman will not provide any gain.

Unless the dynamic huffman tree is already initialized with some kind of
tree... though it will probably still have cases where it produces a longer
bit stream for small bits of information.

Statis huffman can ofcourse not be used because of the dynamic nature of the
variable bit format.

Bye,
Skybuck.

 

[Skybuck Flying]

How do you know it hasn't been thought of before, but rapidly rejected,
without being published, for excessive inefficiency? N-1 zero bits
followed by a 1 is among the least efficient known representations of
the number N.

Define inefficiency... you mention space inefficiency.

However it's simple, it's fast, it can be interleaved etc, it's flexible.

So it has nice properties which would have ment it was worth publicizing
about

Somebody else said it hasn't been thought of yet... I'll take his word for
it

Until proven otherwise

Bye,
Skybuck.