So, I've been sort of reading this:

http://download.intel.com/design/intarch/manuals/27320401.pdf

I've had a pretty good idea of how the 8086 and 8088 deal with the 
system bus. But, I wanted to understand more about the later generation 
processors, so I started with the Pentium.

I'm on the section dealing with bus arbitration and cache coherency when 
there are 2 processors in the system. (This is the embedded version, I'm 
not sure if the full version is all that different)

It occurs to me that handling the cache when there are 2 parts vying for 
the same resource can get rather messy.

What I understand so far is: One process has the bus, and either reads 
or writes from/to the bus. The other processor watches the activity and, 
if it sees an address it has modified it tells the other processor, 
which passes bus control to the other, puts the data out on the bus, 
then returns control to the first processor.

Apparently, the bus can also be pipelined. I'm not exactly sure how this 
works, but the processors then have to agree on whether the operation 
actually can be put in a pipeline.

I can definitely see some potential for bottle-necks in a 
multi-processor system when dealing with the bus, since electrically, 
only one device can place data on the bus at one time. The nice thing 
is, in system design, you can design your bus the same for single or 
dual processors. Provided you've wired the proper signals together, and 
initialized the processors properly with software and certain pin 
levels, it's totally transparent to the rest of the system.

-- 
~Mike

Post a reply to this message

On 02/06/2011 03:06 PM, Mike Raiford wrote:
> So, I've been sort of reading this:
>
> http://download.intel.com/design/intarch/manuals/27320401.pdf

Woooo boy, that's one big can of complexity, right there! ;-)

> I've had a pretty good idea of how the 8086 and 8088 deal with the
> system bus. But, I wanted to understand more about the later generation
> processors, so I started with the Pentium.

I'm going to sound really old now, but... I remember back in the days 
when the RAM was faster than the CPU. I remember in-order execution 
without pipelines. When I first sat down to read about how modern IA32 
processors actually work... I was pretty shocked. The circuitry seems to 
spend more time deciding how to execute the code than actually, you 
know, *executing* it! o_O

> I'm on the section dealing with bus arbitration and cache coherency when
> there are 2 processors in the system.

> It occurs to me that handling the cache when there are 2 parts vying for
> the same resource can get rather messy.

 > I can definitely see some potential for bottle-necks in a
 > multi-processor system when dealing with the bus, since electrically,
 > only one device can place data on the bus at one time. The nice thing
 > is, in system design, you can design your bus the same for single or
 > dual processors. Provided you've wired the proper signals together, and
 > initialized the processors properly with software and certain pin
 > levels, it's totally transparent to the rest of the system.

There are two main problems with trying to connect two CPUs to one RAM 
block:

1. Bandwidth.

2. Cache coherence.

Currently, RAM is way, way slower than the CPU. Adding more CPU cores 
simply makes things worse. Unless you're doing a specific type of 
compute-heavy process that doesn't require much RAM access, all you're 
doing is taking the system's main bottleneck and making it twice as bad. 
Instead of having /one/ super-fast CPU sitting around waiting for RAM to 
respond, now you have /two/ super-fast CPUs fighting over who gets to 
access RAM next.

(I've seen plenty of documentation from the Haskell developers where 
they benchmark something, and then find that it goes faster if you turn 
*off* parallelism, because otherwise the multiple cores fight for 
bandwidth or constantly invalidate each other's caches.)

It seems inevitable that the more memory you have, the slower it is. 
Even if we completely ignore issues of cost, bigger memory = more 
address decode logic + longer traces. Longer traces mean more power, 
more latency, more capacitance, more radio interference. It seems 
inevitable that if you have a really huge memory, it will necessarily be 
very slow.

Similarly, if you have huge numbers of processing elements all trying to 
access the same chunk of RAM through the same bus, you're splitting the 
available bandwidth many, many ways. The result isn't going to be high 
performance.

My personal belief is that the future is NUMA. We already have cache 
hierarchies three or four levels deep, backed by demand-paged virtual 
memory. Let's just stop pretending that "memory" is all uniform with 
identical latency and start explicitly treating it as what it is.

Indeed, sometimes I start thinking about what some kind of hyper-Harvard 
architecture would look like. For example, what happens if the machine 
stack is on-chip? (I.e., it exists in its own unique address space, and 
the circuitry for it is entirely on-chip.) What about if there were 
several on-chip memories optimised for different types of operation?

Unfortunately, the answer to all these questions generally ends up being 
"good luck implementing multitasking".

The other model I've looked at is having not a computer with one giant 
memory connected to one giant CPU, but zillions of smallish memories 
connected to zillions of processing elements. The problem with *that* 
model tends to be "how do I get my data to where I need it?"

As someone else once said, "a supercomputer is a device for turning a 
compute-bound problem into an I/O-bound problem".

> What I understand so far is: One process has the bus, and either reads
> or writes from/to the bus. The other processor watches the activity and,
> if it sees an address it has modified it tells the other processor,
> which passes bus control to the other, puts the data out on the bus,
> then returns control to the first processor.

http://en.wikipedia.org/wiki/Cache_coherence
http://en.wikipedia.org/wiki/MESI_protocol

Looks like what you're describing is a "snooping" implementation. There 
are also other ways to implement this.

> Apparently, the bus can also be pipelined. I'm not exactly sure how this
> works, but the processors then have to agree on whether the operation
> actually can be put in a pipeline.

Again, when I learned this stuff, RAM was the fastest thing in the 
system. You just send the address you want on the address bus and read 
back (or write) the data on the data bus.

These days, the CPU is the fastest thing. You can "pipeline" read 
requests by requesting a contiguous block of data. That way, you 
eliminate some of the latency of sending a memory request for each 
datum. (And, let's face it, you only talk to main memory to fill or 
empty cache lines, which are contiguous anyway.)

I understand this also has something to do with the internal way that 
the RAM chips do two-dimensional addressing...

Post a reply to this message

OK... something I don't get. Presumably, it has some weird thing to do 
with alignment.

A bit of background first: The Pentium has a 64-bit data bus. What this 
means is that the lower two bits of the address bus have been dropped. 
Meaning, the processor really only accesses memory on 8 byte boundaries.

But, it has a way of getting around that, it has 8 pins that act as a 
mask. If it only needs the first four bytes, then it can pull low only 
the first four of the BE# pins. This tells the system's logic what it 
wants. This makes accessing smaller chunks of memory much more efficient 
if, say, the RAM is composed of modules that have an 8 bit data bus. Oh, 
by the way... this is why it was critically important to make sure your 
memory is installed in pairs. ;) You see, back in the day DRAM was sold 
in 32 bit modules. With only one module installed, the data bus was only 
32 bits wide (*IF* the motherboard actually supported that 
configuration) but, with both....

But here's the part that isn't making sense to me:

>
+---------------------------------------------------------------------------------------------------------------+
> |Length of Transfer            |1 Byte  |2 Bytes                                    
                           |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |Low Order Address             |xxx     |000     |001     |010     |011     |100    
|101     |110     |111     |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |1st transfer                  |b       |w       |w       |w       |hb      |w      
|w       |w       |hb      |
> |Byte enables driven           |0       |BE0-1#  |BE1–2#  |BE2–3#  |BE4#    |BE4–5# 
|BE5–6#  |BE6–7#  |BE0#    |
> |Value driven on A3            |        |0       |0       |0       |0       |0      
|0       |0       |1       |
>
+------------------------------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
> |2nd transfer (if needed)      |        |        |        |        |lb      |       
|        |lb      |        |
> |Byte enables driven           |        |        |        |        |BE3#    |       
|        |BE7#    |        |
> |Value driven on  A3           |        |        |        |        |0       |       
|        |0       |        |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |Length of Transfer            |4 Bytes                                             
                           |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |Low Order Address             | 000     |001      |010      |011       |100     
|101      |110       |111     |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |1st transfer                  | d       |hb       |hw       |h3        |d       
|hb       | hw       |h3      |
> |Byte enables driven           | BE0–3#  |BE4#     |BE4–5#   |BE4–6#    |BE4–7#  
|BE0#     |BE0–1#    |BE0–2#  |
> |Low order address             | 0       |0        |0        |0         |0        |1
       |1         |1       |
>
+------------------------------+---------+---------+---------+----------+---------+---------+----------+--------+
> |2nd transfer (if needed)      |         |l3       |lw       |lb        |        
|l3       |lw        |lb      |
> |Byte enables driven           |         |BE1–3#   |BE2–3#   |BE3#      |        
|BE5–7#   |BE6–7#    |BE7#    |
> |Value driven on A3            |         |0        |0        |0         |         |0
       |0         |0       |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |Length of Transfer            |8 Bytes                                             
                           |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |Low Order Address             | 000     |001      |010      |011       |100     
|101      |110       |111     |
>
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
> |1st transfer                  | q       |hb       |hw       |h3        |hd      
|h5       |h6        |h7      |
> |Byte enables driven           | BE0–7#  |BE0#     |BE0–1#   |BE0–2#    |BE0–3#  
|BE0–4#   |BE0–5#    |BE0–6#  |
> |Value driven on A3            | 0       |1        |1        |1         |1        |1
       |1         |1       |
>
+------------------------------+---------+---------+---------+----------+---------+---------+----------+--------+
> |2nd transfer (if needed)      |         |l7       |l6       |l5        |ld      
|l3       |lw        |lb      |
> |Byte enables driven           |         |BE1–7#   |BE2–7#   |BE3–7#    |BE4–7#  
|BE5–7#   |BE6–7#    |BE7#    |
> |Value driven on A3            |         |0        |0        |0         |0        |0
       |0         |0       |
>
+---------------------------------------------------------------------------------------------------------------+
>
> Key:
>
> b = byte transfer       w = 2-byte transfer     3 = 3-byte transfer     d = 4-byte
transfer
> 5 = 5-byte transfer     6 = 6-byte transfer     7 = 7-byte transfer     q = 8-byte
transfer
> h = high order         ll = low order
>
> 8-byte operand:
>
+----------------------------------------------------------------------------------------+
> | high order byte | byte 7 | byte 6 | byte 5 | byte 4 | byte 3 | byte 2 | low order
byte |
>
+----------------------------------------------------------------------------------------+

OK, so... in this table you can see when the operand is a word it 
requires a second transfer if the low order bits of the address are 3 or 7.

7 is understandable. after all, you're crossing a boundary, there. But, 
3 is utterly baffling.

from this chart, when dealing with word-length operands I can surmise:

Address = # transfers for word
0x12345678 = 1 transfer
0x12345679 = 1 transfer
0x1234567A = 1 transfer
0x1234567B = 2 transfers
0x1234567C = 1 transfer
0x1234567D = 1 transfer
0x1234567E = 1 transfer
0x1234567F = 2 transfer

To me it makes no sense. xxxxB should be able to transfer in one go. Why 
wouldn't it?
-- 
~Mike

Post a reply to this message

On 03/06/2011 02:48 PM, Invisible wrote:

> Woooo boy, that's one big can of complexity, right there! ;-)

I've said it before, and I'll say it again: The IA32 platform is one 
huge stack of backwards compatibility kludges.

The story begins (arguably) with the Intel 8008, released in 1972 or so. 
(!!) It consisted of 3,500 transistors, and was manufactured on a 10 μm 
process PMOS. It ran at 500 kHz. (That's 0.5 MHz or 0.00005 GHz.) It had 
a grand total of 18 pins (despite the 14-bit address space). It featured 
two main registers, A and B, both 8 bits wide.

Then came the 8080 (around 1974), with a 2 MHz maximum clock speed. This 
had 7 registers, named A, B, C, D, H, and L, all 8 bits wide. Certain 
pairs (BC, DE, HL) could be used together for certain instructions to 
perform 16 bit operations.

(The world-famous Z80 processor is an enhanced version of the 8080.)

Now, finally, in 1978 (!) we arrive at the 8086. The A, B, C and D 
registers are renamed AL, BL, CL and DL, and new registers called AH, 
BH, CH and DH were added. These are all 8-bit, and can be combined 
together creating AX, BX, CX and DX registers 16 bits wide.

Also new was the infamous memory segmentation model. Under this bizarre 
scheme, there are four "segment pointer" registers which select which 
"segment" you access data from. But because the segment offsets are 
16-bit, the segments actually overlap, so there are multiple ways to 
refer to the same physical address.

Basically, this is a huge kludge. Rather than implementing real 32-bit 
addressing, they kludged in 20-bit addressing. While not /completely/ 
without merit (e.g., this whole segment melarchy makes relocatable code 
quite a bit easier), it's really a bad solution.

Not content with that, Intel developed the 8087, the FPU to go with the 
8086 CPU. Unlike any sane design, this FPU has 8 registers, but you 
cannot access them directly. Instead, they function as a "stack". Math 
operations "pop" their operands from the top and "push" the result back 
on. If you want to access something lower down, you have to FXCH 
instructions to swap the top register's contents with one of the 
registers lower down.

In later generations of chip, the registers are mapped in hardware with 
pointers, and two parallel instruction pipelines allow you to optimise 
FXCH down to zero clock cycles (effectively). But still, WTF?

In 1982 (this is the first year in the list so far when I was actually 
*live*!) the 80286 (or "286") appeared. This was the first CPU with 
memory protection.

In 1985, the 80386 ("386") came along. This was the first 32-bit 
processor. (Which is why IA32 is sometimes referred to as "i386", and 
why Linux generally refuses to work with anything older.) This was the 
first processor where the relationship between segment numbers and 
physical memory addresses is programmable rather than hard-wired. In 
other words, this is where memory pages got invented.

The 386 inherits all of the registers from the 286 (i.e., AL, AH, AX, 
BL, BH, BX, etc.) But AX is a 16-bit register. So the 386 adds a new 
register, EAX, which is 32 bits. AX is the bottom 16 bits of EAX. 
Similarly for B, C and D.

(By contrast, a *real* 32-bit chip like the Motorola 68000 has registers 
A0 through A7 and D0 through D7, and when you do an operation, you 
specify how many bits to use, e.g., mov.l d3 d7. None of this stupidity 
with multiple names for the same register.)

When AMD64 eventually came along, these became 64-bit registers RAX, 
RBX, etc., of which EAX, EBX, etc. are the lower 32-bits. (AMD64 also 
adds completely new 64-bit registers R8 through R15, just for good 
measure. You would expect this to result in an utterly massive speed 
increase, but apparently people have measured it at less than 2%.)

If I say 80486, you probably think of some ancient old thing. But it was 
the first chip in the family to include an L1 cache, and the first one 
to support superscalar execution (i.e., executing more than one 
instruction per clock cycle). In the form of the 486DX, it was also the 
first one with an on-chip FPU.

In 1996, the Pentium MMX arrived. MMX stands for "multimedia 
extensions". (Remember, in the 1990s, "multimedia" was the wave of the 
future that was going to take over the world...) What this actually 
*does* is it adds SIMD (single-instruction, multiple-data) instructions. 
Basically, there's 8 new registers, MMX0 through MMX7, each 64 bits 
wide. Using the new MMX instructions, you can basically treat a given 
MMX register as an array of values (e.g., 4 items of 16 bits each) and 
do element-wise operations over them.

Nothing wrong with that.

Oh yeah, and the MMX registers are the FPU registers.

KLUDGE! >_<

Yes, rather than add 8 *new* registers, MMX just adds new names for the 
existing FPU registers. (But now you have proper random access to them.) 
The reason for this is simple: it means that the OS doesn't have to 
support MMX for context switches to work properly. (I.e., a context 
switch under an OS that doesn't know about MMX won't clobber the MMX 
registers, because the MMX registers *are* the FPU registers, which any 
FPU-aware OS will already be preserving.)

This horrifying kludge still haunts us to this day. Yes, it meant that 
developers could start using MMX because Microsoft released an updated 
version of Windows. On the other hand, it means you can't use MMX (which 
is integer-only) and normal FPU operations at the same time, because one 
will clobber the other. FAIL!

In 1998, AMD released the 3DNow! technology that almost nobody now 
remembers. This basically adds new MMX operations, using the same "MMX 
registers that are really the FPU registers" kludge, for the same reason.

Apparently 3DNow! was never that popular, and is being phased out now. 
Instead, Intel came up with SSE, which adds new registers named XMM. 
(Get it?) Yes, that's right, *finally* they actually added new registers 
rather than kludging old ones. These new XMM registers are 128 bits 
wide, and can be operated as 4 x single-precision floats.

Then SSE2 came along, and added versions of all the MMX instructions 
that work on the XMM registers instead. So now you never need to use the 
old MMX instructions ever again! And now the XMM registers can be 
treated not just as 2 x single-precision floats, but also as (say) 2 x 
double-precision floats, 8 x 16-bit integers, and so on.

Of course, since the OS has to know to include the new XMM registers in 
context switches, SSE is disabled by default. The OS has to explicitly 
enable it before it will work. A bit like the way the processor starts 
up in "real mode" (i.e., 8086 emulation mode), and the OS has to 
manually switch it into "protected mode" (i.e., the normal operating 
mode that all modern software actually freaking uses) during the boot 
sequence.

Then we have AMD64, which runs in 32-bit mode by default until the OS 
switches it to 64-bit mode. (The PC I am using right now is *still* 
running in 32-bit mode, despite possessing a 64-bit processor.) In that 
mode, an extra 8 XMM registers appear (XMM8 to XMM15).

Did you follow all that?

Don't even get me started on all the different memory paging and 
segmentation schemes...

In short, they kept kludging more and more stuff in. Having a 
stack-based FPU register file is a stupid, stupid idea. But now all our 
software depends on this arrangement, so we're stuck with it forever. 
Aliasing the MMX registers to the FPU registers was stupid, but 
fortunately we don't have to live with that one. Memory segmentation was 
stupid, but now we're basically stuck with it. The list goes on...

Post a reply to this message

On 6/3/2011 8:48 AM, Invisible wrote:
> On 02/06/2011 03:06 PM, Mike Raiford wrote:
>> So, I've been sort of reading this:
>>
>> http://download.intel.com/design/intarch/manuals/27320401.pdf
>
> Woooo boy, that's one big can of complexity, right there! ;-)
>
>> I've had a pretty good idea of how the 8086 and 8088 deal with the
>> system bus. But, I wanted to understand more about the later generation
>> processors, so I started with the Pentium.
>
> I'm going to sound really old now, but... I remember back in the days
> when the RAM was faster than the CPU. I remember in-order execution
> without pipelines. When I first sat down to read about how modern IA32
> processors actually work... I was pretty shocked. The circuitry seems to
> spend more time deciding how to execute the code than actually, you
> know, *executing* it! o_O
>

Me, too. I remember (I think it was back in the 386 days) when the 
processors started to outpace some memory, you had to start adding wait 
states in order to keep the processor from spamming the memory with too 
many requests. Now the core operates many times the speed of the bus. 
Everything with a modern multi-core CPU is IO bound.

>> I'm on the section dealing with bus arbitration and cache coherency when
>> there are 2 processors in the system.
>
>> It occurs to me that handling the cache when there are 2 parts vying for
>> the same resource can get rather messy.
>
>> I can definitely see some potential for bottle-necks in a
>> multi-processor system when dealing with the bus, since electrically,
>> only one device can place data on the bus at one time. The nice thing
>> is, in system design, you can design your bus the same for single or
>> dual processors. Provided you've wired the proper signals together, and
>> initialized the processors properly with software and certain pin
>> levels, it's totally transparent to the rest of the system.
>
> There are two main problems with trying to connect two CPUs to one RAM
> block:
>
> 1. Bandwidth.
>
> 2. Cache coherence.
>
> Currently, RAM is way, way slower than the CPU. Adding more CPU cores
> simply makes things worse. Unless you're doing a specific type of
> compute-heavy process that doesn't require much RAM access, all you're
> doing is taking the system's main bottleneck and making it twice as bad.
> Instead of having /one/ super-fast CPU sitting around waiting for RAM to
> respond, now you have /two/ super-fast CPUs fighting over who gets to
> access RAM next.
>
> (I've seen plenty of documentation from the Haskell developers where
> they benchmark something, and then find that it goes faster if you turn
> *off* parallelism, because otherwise the multiple cores fight for
> bandwidth or constantly invalidate each other's caches.)

The solution, of course would be to break the task down into small 
blocks that can fit within the CPUs' caches (good locality) and work on 
units that are in areas of memory where cache lines will not overlap. 
Which is all fine and good, but ... not really feasable because you are 
not in charge of where your task's pages physically reside in memory. 
The OS is in charge of that, and it could change the physical layout at 
any moment.

> It seems inevitable that the more memory you have, the slower it is.
> Even if we completely ignore issues of cost, bigger memory = more
> address decode logic + longer traces. Longer traces mean more power,
> more latency, more capacitance, more radio interference. It seems
> inevitable that if you have a really huge memory, it will necessarily be
> very slow.

Right, because all of those elements work against you. It still amazes 
me that a CPU can operate at the speeds it does and still run robustly 
enough to produce good results without completely distorting the signals 
it's handling. Each FET has a capacitance at the gate. They've managed 
to get the total capacitance (traces, gates, etc) so tiny that it 
doesn't kill the signal.

> Similarly, if you have huge numbers of processing elements all trying to
> access the same chunk of RAM through the same bus, you're splitting the
> available bandwidth many, many ways. The result isn't going to be high
> performance.
>
> My personal belief is that the future is NUMA. We already have cache
> hierarchies three or four levels deep, backed by demand-paged virtual
> memory. Let's just stop pretending that "memory" is all uniform with
> identical latency and start explicitly treating it as what it is.
>
> Indeed, sometimes I start thinking about what some kind of hyper-Harvard
> architecture would look like. For example, what happens if the machine
> stack is on-chip? (I.e., it exists in its own unique address space, and
> the circuitry for it is entirely on-chip.) What about if there were
> several on-chip memories optimised for different types of operation?

Don't some RISC processors sort of do this?

> Unfortunately, the answer to all these questions generally ends up being
> "good luck implementing multitasking".
>
> The other model I've looked at is having not a computer with one giant
> memory connected to one giant CPU, but zillions of smallish memories
> connected to zillions of processing elements. The problem with *that*
> model tends to be "how do I get my data to where I need it?"

Right.. There would need to be some sort of controller that could 
transfer data from Block A to Block B. Addressing would be quite ... 
interesting in this scheme.

> As someone else once said, "a supercomputer is a device for turning a
> compute-bound problem into an I/O-bound problem".
>

Pretty much. Unless you're working on something that can fit entirely 
inside the processing units' caches, you'll have exactly that problem.

>> What I understand so far is: One process has the bus, and either reads
>> or writes from/to the bus. The other processor watches the activity and,
>> if it sees an address it has modified it tells the other processor,
>> which passes bus control to the other, puts the data out on the bus,
>> then returns control to the first processor.
>
> http://en.wikipedia.org/wiki/Cache_coherence
> http://en.wikipedia.org/wiki/MESI_protocol
>

Wow. I actually recognized MESI right off: Modified, Exclusive, Shared, 
Invalid. This is exactly what the Pentium uses.

> Looks like what you're describing is a "snooping" implementation. There
> are also other ways to implement this.

Yep. exactly, the LRM snoops the MRM's activity. If it sees that the MRM 
is writing or reading a line that the LRM has marked as modified or 
exclusive, then it signals the MRM that it needs the bus to write out 
what it has.

>
> These days, the CPU is the fastest thing. You can "pipeline" read
> requests by requesting a contiguous block of data. That way, you
> eliminate some of the latency of sending a memory request for each
> datum. (And, let's face it, you only talk to main memory to fill or
> empty cache lines, which are contiguous anyway.)
>

OK, So... essentially, this is burst mode.

> I understand this also has something to do with the internal way that
> the RAM chips do two-dimensional addressing...

I can't remember the specifics, at the moment.

-- 
~Mike

Post a reply to this message

>> I'm going to sound really old now, but... I remember back in the days
>> when the RAM was faster than the CPU. I remember in-order execution
>> without pipelines. When I first sat down to read about how modern IA32
>> processors actually work... I was pretty shocked. The circuitry seems to
>> spend more time deciding how to execute the code than actually, you
>> know, *executing* it! o_O
>
> Me, too. I remember (I think it was back in the 386 days) when the
> processors started to outpace some memory, you had to start adding wait
> states in order to keep the processor from spamming the memory with too
> many requests. Now the core operates many times the speed of the bus.
> Everything with a modern multi-core CPU is IO bound.

Well, I suppose if you want to be picking, it's not bound by I/O 
operations, it's bound by RAM bandwidth and/or latency.

Current trends seem to be towards increasing RAM bandwidth to greater 
and greater amounts, at the expense of also increasing latency. If your 
caches and pipelines and prefetch and branch prediction manage to hige 
the latency, that's fine. If they don't... SLOOOOOW!

There was a time when the CPU core was only a dozen times faster than 
RAM. Those days are gone. Last I heard, if the CPU needs to access main 
memory, you're talking about a 400 clock cycle stall.

At this point, increasing clock speed or adding more cores simply 
increases the amount of time the CPU spends waiting. Even the faster 
memory connections only increase the bandwidth /of the interface/. The 
actual RAM cells aren't getting any faster.

>> (I've seen plenty of documentation from the Haskell developers where
>> they benchmark something, and then find that it goes faster if you turn
>> *off* parallelism, because otherwise the multiple cores fight for
>> bandwidth or constantly invalidate each other's caches.)
>
> The solution, of course would be to break the task down into small
> blocks that can fit within the CPUs' caches (good locality) and work on
> units that are in areas of memory where cache lines will not overlap.

Sometimes this is possible. For example, the latest releases of the 
Haskell run-time system have an independent heap per CPU core, and each 
core can run a garbage collection cycle of its own local heap 
independently of the other cores. Since the heaps never overlap, there's 
no problem here.

The *problem* of course happens when data migrates from the generation-1 
area into the shared generation-2 heap area. Then suddenly you have to 
start worrying about cores invalidating each other's caches and so 
forth. Again, the GC engine uses a block-based system to try to minimise 
this.

Another example: A Haskell thread can generate "sparks" which are tasks 
which can usefully be run in the background. But the developers found 
that if you let /any/ core do so, it tends to slow down rather than 
speed up. Basically, it's best to keep sparks local to the core that 
created them, unless there are cores actually sitting idle.

> Which is all fine and good, but ... not really feasable because you are
> not in charge of where your task's pages physically reside in memory.
> The OS is in charge of that, and it could change the physical layout at
> any moment.

Almost every OS known to Man exposes RAM to the application as a linear 
range of virtual addresses. No two [writeable] pages in your 
application's virtual address space will ever map to the same physical 
address.

>> It seems inevitable that the more memory you have, the slower it is.
>> Even if we completely ignore issues of cost, bigger memory = more
>> address decode logic + longer traces. Longer traces mean more power,
>> more latency, more capacitance, more radio interference. It seems
>> inevitable that if you have a really huge memory, it will necessarily be
>> very slow.
>
> Right, because all of those elements work against you. It still amazes
> me that a CPU can operate at the speeds it does and still run robustly
> enough to produce good results without completely distorting the signals
> it's handling. Each FET has a capacitance at the gate. They've managed
> to get the total capacitance (traces, gates, etc) so tiny that it
> doesn't kill the signal.

Over the distances inside a chip, it's not too bad. If the signal has to 
leave the chip, suddenly the distances, the capacitance, the 
interference, the power requirements increase by an order of magnitude. 
That's why you can have a 2.2 GHz L1 cache, but you have a piffling 0.1 
GHz RAM bus.

>> Indeed, sometimes I start thinking about what some kind of hyper-Harvard
>> architecture would look like. For example, what happens if the machine
>> stack is on-chip? (I.e., it exists in its own unique address space, and
>> the circuitry for it is entirely on-chip.) What about if there were
>> several on-chip memories optimised for different types of operation?
>
> Don't some RISC processors sort of do this?

Certainly there are chips that have used some of these ideas. DSP chips 
often have separate address spaces for code and data, and sometimes 
multiple buses too. It tends not to be used for desktop processors though.

(Hell, anything that isn't 8086-compatible tends not to be used for 
desktop processors! Which is a shame, because 8086 isn't that good...)

>> The other model I've looked at is having not a computer with one giant
>> memory connected to one giant CPU, but zillions of smallish memories
>> connected to zillions of processing elements. The problem with *that*
>> model tends to be "how do I get my data to where I need it?"
>
> Right.. There would need to be some sort of controller that could
> transfer data from Block A to Block B. Addressing would be quite ...
> interesting in this scheme.

It's quite feasible that the processing elements themselves would 
organise forwarding messages to where they need to go. You don't 
necessarily need dedicated switching and routing circuitry.

The trouble, of course, is that as the number of processing elements 
increases, either the number of buses increases geometrically, or the 
communications latency increases geometrically. One or the other.

I gather that several supercomputers make use of AMD Opteron chips.

http://en.wikipedia.org/wiki/Jaguar_%28computer%29

The Opteron is a bit unusual:

http://en.wikipedia.org/wiki/Opteron#Multi-processor_features

http://www.amd.com/us/products/technologies/direct-connect-architecture/Pages/direct-connect-architecture.aspx

Basically, each time you add a new chip, you're adding new buses too, 
increasing bandwidth. The Opteron has a limit of 8 CPUs per motherboard; 
Wikipedia claims you can buy "expensive routing chips" to extend this.

>>> What I understand so far is: One process has the bus, and either reads
>>> or writes from/to the bus. The other processor watches the activity and,
>>> if it sees an address it has modified it tells the other processor,
>>> which passes bus control to the other, puts the data out on the bus,
>>> then returns control to the first processor.
>>
>> http://en.wikipedia.org/wiki/Cache_coherence
>> http://en.wikipedia.org/wiki/MESI_protocol
>>
>
> Wow. I actually recognized MESI right off: Modified, Exclusive, Shared,
> Invalid. This is exactly what the Pentium uses.

This is exactly what almost all systems of this kind do.

Post a reply to this message

Am 03.06.2011 16:45, schrieb Invisible:

> In 1982 (this is the first year in the list so far when I was actually
> *live*!) the 80286 (or "286") appeared. This was the first CPU with
> memory protection.
>
> In 1985, the 80386 ("386") came along. This was the first 32-bit
> processor. (Which is why IA32 is sometimes referred to as "i386", and
> why Linux generally refuses to work with anything older.) This was the
> first processor where the relationship between segment numbers and
> physical memory addresses is programmable rather than hard-wired. In
> other words, this is where memory pages got invented.

Not really; IIRC the first x86 processor to introduce programmable 
mapping of logical addresses to physical memory was the 80286; it could 
only do this on a per-segment basis though.

Post a reply to this message

On 6/3/2011 7:45, Invisible wrote:
> (By contrast, a *real* 32-bit chip like the Motorola 68000 has registers A0
> through A7 and D0 through D7, and when you do an operation,

Which is fine if you're not trying to be assembly-language compatible.

> In short, they kept kludging more and more stuff in. Having a stack-based
> FPU register file is a stupid, stupid idea.

Not when your FPU is a separate chip from your CPU.

> But now all our software depends on this arrangement,

Not any longer. For example, I believe gcc has a command-line switch to say 
"use x87 instructions" instead of loading floats via the MMX instructions.

> Aliasing the MMX registers to the FPU registers was stupid,

No, it saved chip space.

> The list goes on...

It would be nice if it was practical to throw out all software and start 
over every time we had a new idea, wouldn't it? But then, everything would 
be as successful as Haskell. ;-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/3/2011 7:50, Mike Raiford wrote:
> Don't some RISC processors sort of do this?

Actually, all you need to do is accept that maybe C-like/Algol-like 
languages aren't the best approach to programming these types of machines. 
FORTH, for example, is very happy doing bunches of work on the local stack 
before going explicitly out to external memory, and I've seen designs for 
very high-speed FORTH-based chips with 32 or 64 cores per chip that have 
relatively little memory contention because of it.

Go to a language model that's either primitive enough (like FORTH) yet close 
enough to the chip architecture that you can force the programmer to 
structure the algorithm in a way that's efficient, or something high-level 
enough (like Hermes or Haskell perhaps) that a Sufficiently Smart Compiler 
(TM) can restructure the code appropriately.

> Right.. There would need to be some sort of controller that could transfer
> data from Block A to Block B. Addressing would be quite ... interesting in
> this scheme.

This is a well known problem with lots of good solutions, depending on how 
you implement the interconnections. The problem is that lots of algorithms 
are inherently sequential.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/3/2011 6:48, Invisible wrote:
> I'm going to sound really old now, but... I remember back in the days when
> the RAM was faster than the CPU.

The first mainframe I worked on had memory clocked at 8x the CPU speed. 7 
DMA channels for each CPU instruction executed. You could be swapping out 
two processes while bringing in two processes without noticing the load.

Even the Atari 400 had RAM clocked twice the CPU speed.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 06/06/2011 04:59 PM, Darren New wrote:
> On 6/3/2011 7:45, Invisible wrote:
>> (By contrast, a *real* 32-bit chip like the Motorola 68000 has
>> registers A0
>> through A7 and D0 through D7, and when you do an operation,
>
> Which is fine if you're not trying to be assembly-language compatible.

That's amusing. The 68000 is a 16-bit processor, which is 
forwards-compatible with the 68020. You run the same code, but now all 
the 32-bit operations automatically go twice as fast. It doesn't /get/ 
much more compatible than that. (Admittedly later processors did 
introduce a few new instructions that won't work on the older models.)

>> In short, they kept kludging more and more stuff in. Having a stack-based
>> FPU register file is a stupid, stupid idea.
>
> Not when your FPU is a separate chip from your CPU.

In what way does having a bizarre machine model help here?

>> But now all our software depends on this arrangement,
>
> Not any longer. For example, I believe gcc has a command-line switch to
> say "use x87 instructions" instead of loading floats via the MMX
> instructions.

Yeah, but every OS will have to support the old arrangement forever 
more, every VM product will have to support it forever more, and every 
processor design will have to support it forever more.

>> Aliasing the MMX registers to the FPU registers was stupid,
>
> No, it saved chip space.

It's quite clear that the design motivation behind this was not chip 
space but OS support. Compared to the space taken up by huge caches, a 
piffling 7 registers is nothing...

>> The list goes on...
>
> It would be nice if it was practical to throw out all software and start
> over every time we had a new idea, wouldn't it? But then, everything
> would be as successful as Haskell. ;-)

This is precisely why Haskell's unofficial motto is "avoid success at 
all costs". (I.e., once you are successful, you have to *care* about 
backwards compatibility.)

I would argue that backwards compatibility is about balance. On the one 
hand, if you change your entire platform every three minutes, nobody 
will build anything for it. (For example, Java.) On the other hand, if 
you support everything forever, you end up with an unmanageable mess. 
(For example, IA32.)

I keep hoping that some day somebody will come up with a chip design 
that runs crappy old 16-bit MS-DOS stuff under software emulation, but 
runs real Big Boy software that people might give a damn about on a 
platform with a modern, coherant design. But apparently I'm just dreaming...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> Right.. There would need to be some sort of controller that could
>> transfer
>> data from Block A to Block B. Addressing would be quite ...
>> interesting in
>> this scheme.
>
> This is a well known problem with lots of good solutions, depending on
> how you implement the interconnections. The problem is that lots of
> algorithms are inherently sequential.

Sometimes I start thinking like this:

Why do we have computers in the first place?

To do the sorts of calculations that humans suck at.

What sorts of calculations do humans suck at?

Calculations which aren't easily parallelisable.

If this line of logic is correct... um... we may have a problem here.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/6/2011 10:40, Orchid XP v8 wrote:
> On 06/06/2011 04:59 PM, Darren New wrote:
>> On 6/3/2011 7:45, Invisible wrote:
>>> (By contrast, a *real* 32-bit chip like the Motorola 68000 has
>>> registers A0
>>> through A7 and D0 through D7, and when you do an operation,
>>
>> Which is fine if you're not trying to be assembly-language compatible.
>
> That's amusing. The 68000 is a 16-bit processor, which is
> forwards-compatible with the 68020.

But that's because it has the same machine code. I'm talking about the 8086 
being assembler-language compatible with the 8080.

>>> In short, they kept kludging more and more stuff in. Having a stack-based
>>> FPU register file is a stupid, stupid idea.
>>
>> Not when your FPU is a separate chip from your CPU.
>
> In what way does having a bizarre machine model help here?

First, it's not bizarre; it's pretty much how many (for example) VMs define 
their machine language. It's called a zero-address machine. Second, it's 
because the op codes don't need to have register numbers in them, so they 
can be smaller and hence faster to transfer. Most mathematics involving FP 
that you are actually willing to pay extra to speed up wind up being larger 
expressions, I'd wager. Plus, the intermediate registers were 80 bits.

> Yeah, but every OS will have to support the old arrangement forever more,
> every VM product will have to support it forever more, and every processor
> design will have to support it forever more.

That's not all our software. That's a pretty tiny part of a context switch.

>>> Aliasing the MMX registers to the FPU registers was stupid,
>> No, it saved chip space.
>
> It's quite clear that the design motivation behind this was not chip space
> but OS support.

True, in this case. But why would you say "the old OS works with new 
software to take advantage of this feature" is stupid?

> This is precisely why Haskell's unofficial motto is "avoid success at all
> costs". (I.e., once you are successful, you have to *care* about backwards
> compatibility.)

That's why I mentioned Haskell. Unfortunately, real-world companies building 
billion-dollar semiconductor fabs don't get to actively avoid success.

> I keep hoping that some day somebody will come up with a chip design that
> runs crappy old 16-bit MS-DOS stuff under software emulation, but runs real
> Big Boy software that people might give a damn about on a platform with a
> modern, coherant design.

They do. Intel chips are RISCs interpreting IA32 instructions. :-)


-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Am 06.06.2011 19:40, schrieb Orchid XP v8:

> I keep hoping that some day somebody will come up with a chip design
> that runs crappy old 16-bit MS-DOS stuff under software emulation, but
> runs real Big Boy software that people might give a damn about on a
> platform with a modern, coherant design. But apparently I'm just
> dreaming...

That's what Intel tried with the Itanium.

"I'm making a note here: Huge Success."

So for the records, it was AMD who convinced people that a backward 
compatible 64-bit processor would be a much better idea. And it was the 
consumers who bought that message.

In the end it was the users' fear of <Insert Your Favorite 32-bit PC 
Video Game Here> running slower than on their older system that won over 
any rationale.

Post a reply to this message

On 06/06/2011 07:14 PM, clipka wrote:
> Am 06.06.2011 19:40, schrieb Orchid XP v8:
>
>> I keep hoping that some day somebody will come up with a chip design
>> that runs crappy old 16-bit MS-DOS stuff under software emulation, but
>> runs real Big Boy software that people might give a damn about on a
>> platform with a modern, coherant design. But apparently I'm just
>> dreaming...
>
> That's what Intel tried with the Itanium.
>
> "I'm making a note here: Huge Success."

As far as I can tell, the trouble with Itanium is that it had very, very 
poor performance. This is not much incentive to switch.

(Which is surprising really, because on paper it looks like a really 
good design...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Am 06.06.2011 20:07, schrieb Orchid XP v8:

>> This is a well known problem with lots of good solutions, depending on
>> how you implement the interconnections. The problem is that lots of
>> algorithms are inherently sequential.
>
> Sometimes I start thinking like this:
>
> Why do we have computers in the first place?
>
> To do the sorts of calculations that humans suck at.
>
> What sorts of calculations do humans suck at?
>
> Calculations which aren't easily parallelisable.
>
> If this line of logic is correct... um... we may have a problem here.

Fortunately it isn't.

Humans suck at /any/ calculations requiring higher degree of precision 
than rule-of-thumb estimates. The human brain is "designed" to work 
/despite/ uncertainties rather than avoid or eliminate them.

However, humans also suck at understanding systems, and are much better 
at understanding single entities working on a problem sequentially. At 
least that's typically true for men - maybe the next generation of 
computers needs women as software developers.

Post a reply to this message

>> If this line of logic is correct... um... we may have a problem here.
>
> Fortunately it isn't.
>
> Humans suck at /any/ calculations requiring higher degree of precision
> than rule-of-thumb estimates. The human brain is "designed" to work
> /despite/ uncertainties rather than avoid or eliminate them.
>
> However, humans also suck at understanding systems, and are much better
> at understanding single entities working on a problem sequentially. At
> least that's typically true for men - maybe the next generation of
> computers needs women as software developers.

I don't think I agree with any of this.

Pick any two locations in London. Ask a London cabbie how to get from 
one to the other. I guarantee they can do it faster than any satnav 
computer.

Pick up a picture of Harrison Ford. Show it to a bunch of people. Almost 
all of them will instantly be able to tell you who it's a picture of. 
Now try getting a computer to figure that out. Good luck with that.

The human brain is really very, very good at certain tasks. Quite 
astonishingly good, when you actually think about it. But it's very bad 
at certain other tasks.

I think of it as being a bit like GPGPU. The brain is a special-purpose 
computational device which is absurdly good at the tasks its designed 
for, and quite bad at everything else. To get good performance on other 
problems, you have to artificially transform them into a problem that 
"looks like" one they're good at. (A bit like the way GPGPU originally 
meant encoding your data as video textures before you can process it.) 
There are people in the Guinness Book of Records who can do crazy things 
like compute the 72nd root of a 15-digit number in their head in under 
10 seconds. It's just that most people can't do that.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> In what way does having a bizarre machine model help here?
>
> First, it's not bizarre; it's pretty much how many (for example) VMs
> define their machine language. It's called a zero-address machine.
> Second, it's because the op codes don't need to have register numbers in
> them, so they can be smaller and hence faster to transfer. Most
> mathematics involving FP that you are actually willing to pay extra to
> speed up wind up being larger expressions, I'd wager. Plus, the
> intermediate registers were 80 bits.

I suppose if you had a really deep stack, this might make sense. You 
could just keep subexpressions on the stack in their natural order, and 
everything would be fine. Unfortunately, 7 deep is nowhere near enough. 
You end up needing to constantly rearrange the data to avoid spilling 
registers back to main memory. (The only explanation I can come up with 
is that if RAM is faster than CPU, spilling is no biggie.)

>> It's quite clear that the design motivation behind this was not chip
>> space
>> but OS support.
>
> True, in this case. But why would you say "the old OS works with new
> software to take advantage of this feature" is stupid?

Kludging the design in a way which will haunt us forever just to get a 
product to market a few months faster sounds pretty stupid to me.

>> This is precisely why Haskell's unofficial motto is "avoid success at all
>> costs". (I.e., once you are successful, you have to *care* about
>> backwards compatibility.)
>
> That's why I mentioned Haskell. Unfortunately, real-world companies
> building billion-dollar semiconductor fabs don't get to actively avoid
> success.

Fortunately, Haskell gave up avoiding success some time ago...

>> I keep hoping that some day somebody will come up with a chip design that
>> runs crappy old 16-bit MS-DOS stuff under software emulation, but runs
>> real
>> Big Boy software that people might give a damn about on a platform with a
>> modern, coherant design.
>
> They do. Intel chips are RISCs interpreting IA32 instructions. :-)

In other words, they are RISC chips with none of the advantages of RISC.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Am 06.06.2011 20:27, schrieb Orchid XP v8:
> On 06/06/2011 07:14 PM, clipka wrote:
>> Am 06.06.2011 19:40, schrieb Orchid XP v8:
>>
>>> I keep hoping that some day somebody will come up with a chip design
>>> that runs crappy old 16-bit MS-DOS stuff under software emulation, but
>>> runs real Big Boy software that people might give a damn about on a
>>> platform with a modern, coherant design. But apparently I'm just
>>> dreaming...
>>
>> That's what Intel tried with the Itanium.
>>
>> "I'm making a note here: Huge Success."
>
> As far as I can tell, the trouble with Itanium is that it had very, very
> poor performance. This is not much incentive to switch.
>
> (Which is surprising really, because on paper it looks like a really
> good design...)

Surprising?

The concept relied heavily on compile-time optimization, which may still 
have had room for optimization back then.

The CPU was designed to work with RAMbus, which turned out to have 
serious initial performance problems on the RAM chip side, and AFAIK 
never managed to catch up with improvements on the DDR protocol.

The CPU was a fairly fresh start, so there may have been significantly 
more room for improvement in the chip design than in contemporary x86 
designs.

I'm also not sure whether it was "very, very" poor performance.

Post a reply to this message

Am 06.06.2011 20:39, schrieb Orchid XP v8:
>>> If this line of logic is correct... um... we may have a problem here.
>>
>> Fortunately it isn't.
>>
>> Humans suck at /any/ calculations requiring higher degree of precision
>> than rule-of-thumb estimates. The human brain is "designed" to work
>> /despite/ uncertainties rather than avoid or eliminate them.
>>
>> However, humans also suck at understanding systems, and are much better
>> at understanding single entities working on a problem sequentially. At
>> least that's typically true for men - maybe the next generation of
>> computers needs women as software developers.
>
> I don't think I agree with any of this.
>
> Pick any two locations in London. Ask a London cabbie how to get from
> one to the other. I guarantee they can do it faster than any satnav
> computer.
>
> Pick up a picture of Harrison Ford. Show it to a bunch of people. Almost
> all of them will instantly be able to tell you who it's a picture of.
> Now try getting a computer to figure that out. Good luck with that.

Not a contradiction to my point; note that /those/ types of 
"calculations" require almost exactly the /opposite/ of precision. Which 
is the domain /computers/ suck at.

For instance, the answers from the people to whom you show the Harrison 
Ford photograph will probably often contain phrases such as "I /think/ 
that's Harrison Ford": They fail at identifying him beyond any doubt 
(i.e. /exactly/), and instead identify him with a certain "error margin".

Likewise, the London cabbie will /not/ pick /the/ fastest route. He'll 
just pick a "sufficiently fast" route. Based not on parameters that can 
be exactly quantified, but on experience and intuition. And not because 
he /knows/ the route to be fast, but because he's /sufficiently 
convinced/ it is.

> The human brain is really very, very good at certain tasks. Quite
> astonishingly good, when you actually think about it. But it's very bad
> at certain other tasks.

Exactly. And among those "certain other tasks" is virtually anything 
involving precise computations.

> There are people in the Guinness Book of Records who can do crazy things
> like compute the 72nd root of a 15-digit number in their head in under
> 10 seconds. It's just that most people can't do that.

Yes, you /can/ train a human to do high-precision calculations. But 
you'd need a huge number of such people (and a REALLY HUGE supply of 
coffee :-)) to perform even the simplest multi-step calculations that way.

Post a reply to this message

>> I don't think I agree with any of this.
>>
>> Pick any two locations in London. Ask a London cabbie how to get from
>> one to the other. I guarantee they can do it faster than any satnav
>> computer.
>>
>> Pick up a picture of Harrison Ford. Show it to a bunch of people. Almost
>> all of them will instantly be able to tell you who it's a picture of.
>> Now try getting a computer to figure that out. Good luck with that.
>
> Not a contradiction to my point; note that /those/ types of
> "calculations" require almost exactly the /opposite/ of precision. Which
> is the domain /computers/ suck at.

>> The human brain is really very, very good at certain tasks. Quite
>> astonishingly good, when you actually think about it. But it's very bad
>> at certain other tasks.
>
> Exactly. And among those "certain other tasks" is virtually anything
> involving precise computations.

To quote myself again: I don't agree with any of this.

Try walking across the room. Trust me, this requires some pretty damned 
precise computations. Don't believe me? Drink some alcohol, and try the 
same task. Hard, isn't it? You know robotics engineers have struggled 
for years to make a bipedal robot that can perform the same apparently 
trivial task?

Balance is hard. A few grams one side or the other and you fall over. 
That sounds pretty precise to me. And yet people ride bicycles. How many 
robots have you seen ride a bicycle?

You say people can't recognise a familiar face with /certainty/, but I 
reject that. A computer might look at a face and rate the probability of 
it belonging to various people, but when I see a person I know, I *know* 
exactly who I'm looking at. Instantly. What's more, when I see a 
computer-generated image of Davy Jones, I recognise it as resembling 
Bill Nighy. How many computer facial recognition programs can do that? 
Again, sounds pretty damned accurate to me.

There are computer programs that compute a "fingerprint" of a piece of 
music, and can supposedly recognise the same recording that has been 
altered slightly. But a human listener can recognise the same piece of 
music performed by a completely different group, and a totally unrelated 
style. No computer can do that. And it's not just that humans use more 
"fuzzy" and less "precise" matching to do their recognition; if that 
were the case, the matching would just be really unreliable. But 
actually, humans are REALLY FRIGGING GOOD at this stuff.

Post a reply to this message

On 6/7/2011 1:37, Invisible wrote:
> But a human listener can recognise the same piece of music
> performed by a completely different group, and a totally unrelated style. No
> computer can do that.

This is incorrect. I watched our server listen to someone singing 
"Yesterday" on American Idol and our computer correctly recognizing it as a 
Beatles song.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Try walking across the room. Trust me, this requires some pretty damned
> precise computations. Don't believe me? Drink some alcohol, and try the
> same task. Hard, isn't it? You know robotics engineers have struggled
> for years to make a bipedal robot that can perform the same apparently
> trivial task?
>
> Balance is hard. A few grams one side or the other and you fall over.
> That sounds pretty precise to me. And yet people ride bicycles. How many
> robots have you seen ride a bicycle?
>
> You say people can't recognise a familiar face with /certainty/, but I
> reject that. A computer might look at a face and rate the probability of
> it belonging to various people, but when I see a person I know, I *know*
> exactly who I'm looking at. Instantly. What's more, when I see a
> computer-generated image of Davy Jones, I recognise it as resembling
> Bill Nighy. How many computer facial recognition programs can do that?
> Again, sounds pretty damned accurate to me.
>
> There are computer programs that compute a "fingerprint" of a piece of
> music, and can supposedly recognise the same recording that has been
> altered slightly. But a human listener can recognise the same piece of
> music performed by a completely different group, and a totally unrelated
> style. No computer can do that. And it's not just that humans use more
> "fuzzy" and less "precise" matching to do their recognition; if that
> were the case, the matching would just be really unreliable. But
> actually, humans are REALLY FRIGGING GOOD at this stuff.

You have a grave misconception here:
As has been said before, the human brain is anything but precise. It actually is
very very good at correcting errors and adapting to them. Walking
across a room is not a precalculated series of movements like it would be for
most robots. The brain is constantly regulating all your movements dependent on
the millions of information it receives from your body.
Whenever anything happens that's not quite as it was "planned" it will just
change the movement slightly without your conciousness even noticing.

Facial recognition is much the same. The human brain has dedicated structures
for exactly that purpose. If they are damaged, the person suddenly can't
recognize faces anymore. I once saw a report about someone having a stroke and
losing this ability. He was unable to relearn this ability, because the
"dedicated hardware" could not be "emulated in software", so to speak. Those
dedicated structures have evolved over millenia for this one single purpose. You
cannot expect a computer to perform with the same efficiency on a general
purpose processor.

And about accuracy of facial recognition:
How sure you are about recognizing someone depends largely on how well you know
that person and if there's other persons you know that look alike. If someone
has a distinct face than your confidence of recognition is high. But if you look
at identical twins you'll be less sure of recognizing them correctly.
So how can you say you are 100% sure you recognized someone? It's just that your
confidence is high enough for you to think you are 100% sure.

Regards
Aydan

Post a reply to this message

On 07/06/2011 04:28 PM, Aydan wrote:

> Walking
> across a room is not a precalculated series of movements like it would be for
> most robots.

...which is why the robot is wrong. The *correct* way to navigate 
unknown terrain is to constantly monitor and adapt to your surroundings.

> Whenever anything happens that's not quite as it was "planned" it will just
> change the movement slightly without your conciousness even noticing.

Yes. And these changes are very, very precise. If they weren't, you'd 
fall over. The fact that it does this in a feedback loop doesn't negate 
the need for very exact, very fine controls.

> Facial recognition is much the same. The human brain has dedicated structures
> for exactly that purpose. If they are damaged, the person suddenly can't
> recognize faces anymore.

Like I said: The human brain is an elaborate special-purpose 
computational device which is ridiculously good at the things it's 
designed for, and drastically less good at the things it isn't designed for.

> And about accuracy of facial recognition:
> How sure you are about recognizing someone depends largely on how well you know
> that person and if there's other persons you know that look alike.

People have actually done research on this. The vast majority of people 
recognise other people with stunning accuracy. Not that they /think/ 
they do, but that you can actually /measure/ this.

That said, it's also been found that people from a different ethnic 
group tend to look more uniform to you than they do to people belonging 
to that ethnic group. Whether this is a genetic or environmental thing 
is a subject of some debate. (Although it seems quite reasonable to me 
that it's simply a calibration issue.)

Post a reply to this message

>> But a human listener can recognise the same piece of music
>> performed by a completely different group, and a totally unrelated
>> style. No computer can do that.
>
> This is incorrect. I watched our server listen to someone singing
> "Yesterday" on American Idol and our computer correctly recognizing it
> as a Beatles song.

This would be a rather stunning result for AI. Last time I checked, AI 
is poor to the point of being utterly useless for most if not all 
recognition tasks. Even something trivial like OCR doesn't work very 
well yet.

Post a reply to this message

On 6/7/2011 8:28, Aydan wrote:
> confidence is high enough for you to think you are 100% sure.

Or, more precisely, you can be 100% sure and still be wrong. :-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/7/2011 8:39, Invisible wrote:
> This would be a rather stunning result for AI.

It wasn't even what you'd call AI nowadays. It was just pattern matching.

Why are you using the subjunctive, as if this is a fictional story?

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 07/06/2011 04:40 PM, Darren New wrote:
> On 6/7/2011 8:28, Aydan wrote:
>> confidence is high enough for you to think you are 100% sure.
>
> Or, more precisely, you can be 100% sure and still be wrong. :-)

If you want to split hairs, even events with probability 1 can fail to 
happen. (Contrary to what your introductory statistics book probably 
told you...)

Post a reply to this message

On 07/06/2011 04:41 PM, Darren New wrote:
> On 6/7/2011 8:39, Invisible wrote:
>> This would be a rather stunning result for AI.
>
> It wasn't even what you'd call AI nowadays. It was just pattern matching.

Given that two different, unrelated recordings of the same piece of 
music have entirely unrelated waveforms, I'm not sure how you can claim 
that simple pattern matching would find such a complex similarity.

> Why are you using the subjunctive, as if this is a fictional story?

Damnit, now I have to go look up what a "subjunctive" is...

Post a reply to this message

On 07/06/2011 04:45 PM, Invisible wrote:

> Damnit, now I have to go look up what a "subjunctive" is...

NAAAARGH! IT BURNS! >_<

Post a reply to this message

On 6/7/2011 8:45, Invisible wrote:
> I'm not sure how you can claim that
> simple pattern matching would find such a complex similarity.

I'm not saying it would. I'm saying it *did*.

>> Why are you using the subjunctive, as if this is a fictional story?
> Damnit, now I have to go look up what a "subjunctive" is...

Yep.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> On 07/06/2011 04:28 PM, Aydan wrote:
>
> > Walking
> > across a room is not a precalculated series of movements like it would be for
> > most robots.
>
> ...which is why the robot is wrong. The *correct* way to navigate
> unknown terrain is to constantly monitor and adapt to your surroundings.
>
> > Whenever anything happens that's not quite as it was "planned" it will just
> > change the movement slightly without your conciousness even noticing.
>
> Yes. And these changes are very, very precise. If they weren't, you'd
> fall over. The fact that it does this in a feedback loop doesn't negate
> the need for very exact, very fine controls.

I'd say the changes are NOT precise but they are minute and the update rate is
fast. So fast that an error in an update will be negated with the next update
and the control loop is adapted constantly to minimize errors. It's still not
what I would call precise.

If the human body would be capable of precice movement then you should be able
to repeat movements exactly every time you do them. But that's not how it turns
out.
Try throwing a ball at something. You won't be able to hit the same spot twice
in a row. If you practice very very hard, you might get close but you still
won't hit the same spot every time.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> On 07/06/2011 04:41 PM, Darren New wrote:
> > On 6/7/2011 8:39, Invisible wrote:
> >> This would be a rather stunning result for AI.
> >
> > It wasn't even what you'd call AI nowadays. It was just pattern matching.
>
> Given that two different, unrelated recordings of the same piece of
> music have entirely unrelated waveforms, I'm not sure how you can claim
> that simple pattern matching would find such a complex similarity.
>
> > Why are you using the subjunctive, as if this is a fictional story?
>
> Damnit, now I have to go look up what a "subjunctive" is...

You're not matching the waveform but the spectrum.

Post a reply to this message

On 6/7/2011 8:57, Aydan wrote:
> Invisible<voi### [at] devnull>  wrote:
>> On 07/06/2011 04:41 PM, Darren New wrote:
>>> On 6/7/2011 8:39, Invisible wrote:
>>>> This would be a rather stunning result for AI.
>>>
>>> It wasn't even what you'd call AI nowadays. It was just pattern matching.
>>
>> Given that two different, unrelated recordings of the same piece of
>> music have entirely unrelated waveforms, I'm not sure how you can claim
>> that simple pattern matching would find such a complex similarity.
>>
>>> Why are you using the subjunctive, as if this is a fictional story?
>>
>> Damnit, now I have to go look up what a "subjunctive" is...
>
> You're not matching the waveform but the spectrum.

Or, in this case, "I went to the store yesterday" followed by "that would be 
cool if it were possible."

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

>> Yes. And these changes are very, very precise. If they weren't, you'd
>> fall over. The fact that it does this in a feedback loop doesn't negate
>> the need for very exact, very fine controls.
>
> I'd say the changes are NOT precise but they are minute and the update rate is
> fast.

That's one valid way to control error, yes. But I still don't think 
that's how the human brain achieves precision, for the most part.

> If the human body would be capable of precice movement then you should be able
> to repeat movements exactly every time you do them.

Yes.

> But that's not how it turns out.

Really?

> Try throwing a ball at something. You won't be able to hit the same spot twice
> in a row. If you practice very very hard, you might get close but you still
> won't hit the same spot every time.

Or how about this: Try pressing the same keys on a keyboard in the same 
complex sequence, with your eyes closed.

Oh, wait... I can actually do that. And I frequently do. On a daily 
basis, in fact. Obviously my brain lacks the "precision" necessary to 
position my fingers to exactly align with the notes even though there's 
no tactile feedback until I actually touch the key...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 07/06/2011 04:58 PM, Darren New wrote:
> On 6/7/2011 8:45, Invisible wrote:
>> I'm not sure how you can claim that
>> simple pattern matching would find such a complex similarity.
>
> I'm not saying it would. I'm saying it *did*.

And if I told you that scientists have come up with a computer program 
that can accurately estimate a person's intelligence from an analysis of 
their DNA, you'd call BS. Even though you don't have a shred of proof 
that it's not true, and there's no logical reason why it's impossible. 
You wouldn't believe it.

And that's why when somebody says "one time I did <insert very unlikely 
thing here>", people tend not to believe it.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/7/2011 10:44, Orchid XP v8 wrote:
> And that's why when somebody says "one time I did <insert very unlikely
> thing here>", people tend not to believe it.

So, you're saying I'm lying?

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Or how about this: Try pressing the same keys on a keyboard in the same
> complex sequence, with your eyes closed.
>
> Oh, wait... I can actually do that. And I frequently do. On a daily
> basis, in fact. Obviously my brain lacks the "precision" necessary to
> position my fingers to exactly align with the notes even though there's
> no tactile feedback until I actually touch the key...

Every time you touch a key you get the feedback you need to compensate for
drift, because you feel if you were to the right or to the left of the key
center or you hit the wrong key entirely.
The same for touch typing on a computer keyboard. You wouldn't be able to do
that on a touchscreen without tactile feedback where the keys actually are.

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Or how about this: Try pressing the same keys on a keyboard in the same
> complex sequence, with your eyes closed.
>
> Oh, wait... I can actually do that. And I frequently do. On a daily
> basis, in fact. Obviously my brain lacks the "precision" necessary to
> position my fingers to exactly align with the notes even though there's
> no tactile feedback until I actually touch the key...

As for precision, try the following experiment:
1. Sit in front of your computer and put your finger on a key.
2. Close your eyes
3. wave aroud wildly with your arms
4. put the finger back on the key from step one.
5. open your eyes
Did you hit the same key? I doubt it.
If you can do that than that's what I'd call precice.
Moving youf finger a few centimeters without watching and hitting a key that is
more than a finger wide is not precise.

Post a reply to this message

On 6/7/2011 10:22 AM, Orchid XP v8 wrote:
> Or how about this: Try pressing the same keys on a keyboard in the same
> complex sequence, with your eyes closed.
>
> Oh, wait... I can actually do that. And I frequently do. On a daily
> basis, in fact. Obviously my brain lacks the "precision" necessary to
> position my fingers to exactly align with the notes even though there's
> no tactile feedback until I actually touch the key...
>
Betting that, sans mechanical failure, or vibration, a robot would wear 
down a very "tiny" spot on each keyboard, following such a complex 
pattern, while humans would have a wider area of wearing. That said, the 
hands, being a high use part, with specific adaptations *may* include 
additional feedback, or more precise control, specifically due to the 
fact that using them *requires* it. Throwing a ball is a bit different, 
it requires larger muscles, more motion, usually doesn't imply/require 
as much precision, and is more dependent on anomalies in the position of 
other limbs, this means a much *larger* number of inputs, more variance, 
and probably less precise control, since you would have to be processing 
feedback for nearly every muscle in the body, to get anything close to 
the same level of precision as your hands, which can remain in a fixed 
position, or resting against something, which minimizes secondary movements.

Post a reply to this message

On 07/06/2011 07:49 PM, Aydan wrote:

> As for precision, try the following experiment:
> 1. Sit in front of your computer and put your finger on a key.
> 2. Close your eyes
> 3. wave aroud wildly with your arms
> 4. put the finger back on the key from step one.
> 5. open your eyes
> Did you hit the same key? I doubt it.

News flash: Robots can't do this either.

For example, a hard drive has a "servo track" recorded on one platter, 
so that the read/write heads can sense where they are, since the voice 
coils that steer the heads can't reliably return to the same location 
with the necessary precision.

This, even though those voice coils are controlled by a normal computer, 
which is capable of doing perfectly "precise" calculations.

This has nothing to do with the precision of the calculations that the 
controller performs, be it a computer or a brain. It's just an inherent 
result of mechanical devices being imprecise.

> If you can do that than that's what I'd call precice.
> Moving your finger a few centimeters without watching and hitting a key that is
> more than a finger wide is not precise.

You don't play a musical instrument, do you?

Let me tell you, the black keys are *narrower* than a human finger. And 
if you're not careful, your fingers slip off the side. Doesn't sound 
very nice...

Anyway, if that fails to convince you, try throwing a ball through a 
hoop. By the time you get any feedback about whether you hit or not, 
it's far too late to do anything about it; you've already let go of the 
ball! And yet, many people manage to throw precisely enough to do this 
reliably.

Similar story for anyone who plays darts, snooker, tennis, ...

Post a reply to this message

On 07/06/2011 07:34 PM, Darren New wrote:
> On 6/7/2011 10:44, Orchid XP v8 wrote:
>> And that's why when somebody says "one time I did <insert very unlikely
>> thing here>", people tend not to believe it.
>
> So, you're saying I'm lying?

I'm saying that if you casually claim to have solved a problem which has 
stumped AI researchers for decades, I'm going to be /slightly sceptical/ 
about it. Which seems quite rational to me...

Post a reply to this message

On 6/8/2011 1:10, Invisible wrote:
> On 07/06/2011 07:34 PM, Darren New wrote:
>> On 6/7/2011 10:44, Orchid XP v8 wrote:
>>> And that's why when somebody says "one time I did <insert very unlikely
>>> thing here>", people tend not to believe it.
>>
>> So, you're saying I'm lying?
>
> I'm saying that if you casually claim to have solved a problem which has
> stumped AI researchers for decades, I'm going to be /slightly sceptical/
> about it. Which seems quite rational to me...

Recognising a tune has stumped researches for decades?

I didn't solve it. The guys who invented MP3 solved it. I just used it to 
build a bigger system, then watched it work.

What's unlikely about a computer figuring out the primary pitches of a 
recorded piece of music, comparing it to the primary pitches of other music, 
and deciding they're the same?  Is that more amazing than tineye?

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> On 07/06/2011 07:49 PM, Aydan wrote:
>
> > As for precision, try the following experiment:
> > 1. Sit in front of your computer and put your finger on a key.
> > 2. Close your eyes
> > 3. wave aroud wildly with your arms
> > 4. put the finger back on the key from step one.
> > 5. open your eyes
> > Did you hit the same key? I doubt it.
>
> News flash: Robots can't do this either.

They absolutely can. Have a look at industrial robots

> For example, a hard drive has a "servo track" recorded on one platter,
> so that the read/write heads can sense where they are, since the voice
> coils that steer the heads can't reliably return to the same location
> with the necessary precision.

That's not a robot

> This, even though those voice coils are controlled by a normal computer,
> which is capable of doing perfectly "precise" calculations.
>
> This has nothing to do with the precision of the calculations that the
> controller performs, be it a computer or a brain. It's just an inherent
> result of mechanical devices being imprecise.

You should not conclude the precision of all possible drive mechanisms from the
precision if a single one.
HDD head positioning is done gearless. This is inherently imprecise.
They did it like that to be fast, reliable (no worn gears), and they knew they
can get the feedbak they need for accuracy.
Industrial robots for example have geared drives and you can have them move from
one positio to another and back to the exact same position without needing
external calibration. This is because they use stepper motors and geared drives
with very little play for exact reproducability of positions.
You can have one of those move for hours and it won't drift.
And it doesn't get feedback if it's still on track either.

> > If you can do that than that's what I'd call precice.
> > Moving your finger a few centimeters without watching and hitting a key that is
> > more than a finger wide is not precise.
>
> You don't play a musical instrument, do you?

No, but in this case it doesn't matter.

> Let me tell you, the black keys are *narrower* than a human finger. And
> if you're not careful, your fingers slip off the side. Doesn't sound
> very nice...

That may be, but does it really matter if you are a  millimeter off?
And let's say you move your hand about 10 cm and can hit a key within a
millimeter. Sounds realistic? That's still only 1% accuracy.
Your printer head for example can do much better. It can position to a fraction
of a millimeter over 20cm. Multiple times. Without recalibrating.
CNC machines can position to less than a tenth of a millimeter over several
meters. They don't get feedback either. They calibrate onec before starting a
process and run through the process without the need to recalibrate.

> Anyway, if that fails to convince you, try throwing a ball through a
> hoop. By the time you get any feedback about whether you hit or not,
> it's far too late to do anything about it; you've already let go of the
> ball! And yet, many people manage to throw precisely enough to do this
> reliably.

Precisely enough? Right.

Even the absolute pros won't be able to hit the hoop all the time exactly in the
center without touching the rim.
Sinking the ball has a much higher probability, because , up to a point it
doesn't matter if you hit the rim, it will still go in.
A basketball has a diameter of about 24cm the hoop has a diameter of about 45cm.
That makes 10 cm of error margin right there.
Let's say you need to hit the hoop within a radius of 15cm from a distance of
say 5 meters.
That's a whopping 3% of accuracy.
Even if you go out to 15m distance youl only be at 1% accuracy.
Not what I'd call accurate in robot terms.
Program a robot to throw the ball and you'll get better precision once you have
it calibrated properly.
That's the big difference: A human can quite confidently throw a ballinto a hoop
from a multitude of positions without much "setup" time.
But once a robot is calibrated to it's position it can hit the target forever.
The human usually can't.

> Similar story for anyone who plays darts, snooker, tennis, ...

OK, next time you are in a Pub with a darts board, have a look at the
"professionals" and how often they actually hit the triple 20 if they want to.

Post a reply to this message

Le 08/06/2011 20:29, Aydan nous fit lire :
>> > News flash: Robots can't do this either.
> They absolutely can. Have a look at industrial robots
> 

Well, in fact, industrial robots have sequences of fixed positions on
end of run for each axis (be it a translation or rotation) to regularly
reassign the reading of their sensors. Usually perform at start-up and
during the production cycle.

(kind of: push motor to maximum right (against physical stop), store
sensor value. push motor to maximum left... store value. Update sensor's
dataset (for interpolating curve of sensor))
For advanced systems, the physical stop can be replaced by video capture
with pattern matching.

Even the coding wheels (alternative binary on strips with different
frequencies) can only be assumed to have an accurate relative value.

And if you know a bit about using a graduated wheel connected to a
screw, you know that you must always measure by moving from the same
direction, as the screw does not fit the bold exactly in both directions.

Post a reply to this message

On 07/06/2011 04:57 PM, Aydan wrote:

> You're not matching the waveform but the spectrum.

And computing the "spectrum" of a time-varying signal is still an open 
research problem.

Post a reply to this message

>> News flash: Robots can't do this either.
>
> They absolutely can. Have a look at industrial robots

We have several robots in our lab. Every single one of them has sensors 
to detect where the various moving parts are. Every single one runs a 
calibration routine of varying degrees of slowness when you turn it on 
and/or reset it.

>> For example, a hard drive has
>
> That's not a robot

Yes it is. So is a washing machine, or a printer, or any other 
electromechanical device of similar complexity.

> You should not conclude the precision of all possible drive mechanisms from the
> precision if a single one.

My point still stands: The fact that a given mechanism isn't very 
precise doesn't mean that the thing controlling it is inherently imprecise.

Post a reply to this message

> What's unlikely about a computer figuring out the primary pitches of a
> recorded piece of music, comparing it to the primary pitches of other
> music, and deciding they're the same?

Here's one for you: Given a recording of a single pure tone, can you 
determine what pitch that is?

Unfortunately, nobody has yet found a way to do this reliably. I've yet 
to find a guitar tuner that can perform this apparently trivial task.

Now, you're telling me that you have something that can take a 
/non-stationary/ wave containing an arbitrarily complex mixture of tones 
that vary over time and actually deduce something meaningful from it?

Further, you're telling me that it can actually do this with such 
reliability that it can even recognise completely different renditions 
of the same piece of music, without false-positives or false-negatives?

That would be a pretty insane result if it were true.

> Is that more amazing than tineye?

I don't know. Does tineye actually /work/?

More to the point, if I draw a rendition of The Wet Bird in pencil, 
would tineye recognise it as the same image? /That/ would be a problem 
of comparable difficulty. I don't doubt that you can probably determine 
whether two slightly different versions of the same image match, or 
whether two slightly different versions of the same sound recording 
match. But completely different versions? That would require some insane AI.

Post a reply to this message

On 6/9/2011 1:12, Invisible wrote:
> On 07/06/2011 04:57 PM, Aydan wrote:
>
>> You're not matching the waveform but the spectrum.
>
> And computing the "spectrum" of a time-varying signal is still an open
> research problem.

Apparently not.

http://en.wikipedia.org/wiki/Spectrogram

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/9/2011 1:34, Invisible wrote:
> Now, you're telling me that you have something that can take a
> /non-stationary/ wave containing an arbitrarily complex mixture of tones
> that vary over time and actually deduce something meaningful from it?

You mean, like Verizon VCast Song ID?
Music Brainz Picard?
Shazam (http://www.shazam.com/)

> Further, you're telling me that it can actually do this with such
> reliability that it can even recognise completely different renditions of
> the same piece of music, without false-positives or false-negatives?

No, I didn't say that.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message