US patent 5,072,369 (http://www.freepatentsonline.com/5072369.html)
describes a means for bridging the communcation from one computer bus
to a second computer bus with particular emphasis on the aspects that
the bridge is (1) mapping between two address spaces and (2) employes
a snooping scheme on the second bus to preserve cache coherency.

I am looking for published works which describe such a system and are
ideally published before Apr. 7, 1988 but work published after that
date but before Apr. 7, 1989 also has value.

Perhaps in the developement of the Futurebus specification such
matters were  discussed and published.  But, of course, other material
is also valuable.

---

Request for Question Clarification by pafalafa-ga on 07 Oct 2005 09:01 PDT

704wil-ga,

I've done quite a few prior art searches here at Google Answers, but
this one is particularly tricky.  There's a long history to the
development of bus caching and coherency technologies, but it's hard
to say which ones truly mirror the patent you mentioned.

You did not say whether or not you've conducted a thorough search yet
of other patents, so this was my starting point.  Do either of these
sound on target:


=====
[from 1985]
DESCRIPTION OF OPERATION OF CACHE MEMORY 14-40...As previously
mentioned, PAC memory 14-408 performs a bus watch or monitoring
function in the manner illustrated by blocks 608-2 through 608- 8.
More specifically, the snoop register and decode circuits 14-450
monitor the requests applied to system bus 12 by other subsystems.
Upon detecting a write to memory request, the circuits 14-450 generate
an output write signal which is applied to PAC memory 14-408. This
causes the 20 physical address page frame number bits of that request
to be loaded into the snoop register part of block 14-450. The write
signal also causes PAC memory 14-408 to interrogate its contents using
the page frame number bits. If no match or hit is detected, the above
operations are repeated..
=====



=====
[from 1987]
A "write-shared" cache circuit for multiprocessor systems maintains
data consistency throughout the system and eliminates non-essential
bus accesses by utilizing additional bus lines between caches of the
system and by utilizing additional logic in order to enhance the
intercache communication. Data is only written through to the system
bus when the data is labeled "shared". A write-miss is read only once
on the system bus in an "invalidate" cycle, and then it is written
only to the requesting cache.
=====


Please give me as much feedback on these as you can, in terms why they
are good or bad finds, in terms of representing prior art.

I look forward to your comments.


pafalafa-ga

---

Clarification of Question by 704wil-ga on 07 Oct 2005 09:50 PDT

pafalafa-ga,

Thank you for your response.  I have done a search of other patents
(which I believe was thorough, but I'm happy to been shown not).  I
found a number of hits which describe the notion of snooping for
maintaining cache coherency.  I also saw hierachical bus systems
(e.g., in a multi-processor machine) where there was both bridging and
snooping.  But what was missing was the notion of mapping between two
distinct address spaces.  In the multiprocessor, to the extent I could
tell, there was a uniform address space.  [Both of the excerpts you
cited also do not seem to contain the notion of mapping].

My gut feeling is that this concept is more likely to be found in
literature outside of prior patents.  It has the feeling to me of
something that someone would have done if they needed to bridge the
buses in two computer systems where one of the buses supported
snooping.  I can see someone doing this and not thinking to patent it.
 So I expect to find prior art in some niche product, or some small
part of some larger project.

Please let me know if the above is unclear or if I can provide you any
additional information.

---

Request for Question Clarification by pafalafa-ga on 07 Oct 2005 10:13 PDT

Thanks...that helps a lot.

Before I leave off on patents, though, please let me know your thought
about this one, from 1988 (post-April, unfortunately):


http://www.freepatentsonline.com/5025365.html


Although it doesn't mention mapping, per se, it seems to describe a
map-like protocol to acheive coherency, especially given momentary
lapses in address coherency as various sub-systems are being updated.


Let me know what you think.

paf

---

Clarification of Question by 704wil-ga on 07 Oct 2005 11:37 PDT

pafalafa-ga,

I have looked at directory oriented caching schemes and the ones I've
read all seem to be missing the aspect of mapping between two address
spaces.  That seems to be the case in US5025365.  Which, I think,  is
what one would expect in a single purpose built system.  If one was
building a multiprocessor system, why complicate things by having to
map addresses?

One might construct an argument by using the virtual address/physical
address relationship as the basis of the mapping.  If one side of the
bridge used virtual address and the other physical...  But that is not
as satifying as finding art more aligned with the present patent.

---

Request for Question Clarification by pafalafa-ga on 07 Oct 2005 12:21 PDT

Thanks.

I think the best way to approach this, is for me to post any near-hits
I get as I find them, and for you to continue to give me your feedback
on them.  You obviously have a much more refined feel for what you
need than I do, so this way, you can just let me know if anything hits
the nail on the head.

It's not the most elegant way to move forward, but I hope it will bear
fruit just the same.

Here's the latest, if I can call it that, from 1987:


=====
PURPOSE:To minimize the substitution of contents of a cache memory in
case of data transfer by specifying systems of a memory unit and a
direct memory access unit.

CONSTITUTION:A memory unit has first and second access systems for a
cache memory, and the first system is a store-in system. When the
second system is adopted, the cache memory is retrieved for the read
operation and data is read out from the cache memory in case of hit
and data is read out from a main memory but is not registered in the
cache memory in case of mishit, and the cache memory is retrieved for
the write operation and data is written only in the cache memory in
case of hit and data is written only in the main memory in case of
mishit. A direct memory access unit is provided with a data transfer
control means which uses a memory access command group including the
second access system to control data transfer between the memory unit
and a unit group. Thus, substitution of contents of the cache memory
is reduced as much as possible in case of data transfer.
=====


Anything?

paf

---

Clarification of Question by 704wil-ga on 07 Oct 2005 13:58 PDT

pafalafa-ga,

My parsing of this excerpt is a cache which has a mode which keeps its
contents from being flushed during certain operations (I expect
something like pure data transfer).  So that doesn't really seem to be
in the ballpark.

Maybe if we should just look at the 1st claim:

---------------
1. An apparatus for providing data communication between first and second buses, 

the first bus providing a first plurality of bus masters connected
thereto with data read and write access to first data storage
locations mapped to separate addresses within a first address space,
wherein one of said first plurality of bus masters writes data to a
first particular one of said first data storage locations by placing
on the first bus an address to which the first particular one of said
first data storage locations is mapped and transmitting the data via
said first bus, and wherein one of said first plurality of bus masters
reads data from a second particular one of said first data storage
locations by placing on the first bus an address to which the second
particular one of said first storage locations is mapped and receiving
data via said first bus,

the second bus providing a second plurality of bus masters connected
thereto with data read and write access to second data storage
locations mapped to separate addresses within a second address space,
wherein one of said second plurality of bus masters writes data to a
first particular one of said second data storage locations by placing
on the second bus an address to which the first particular one of said
second data storage locations is mapped and transmitting the data via
said second bus, and wherein one of said second plurality of bus
masters reads data from a second particular one of said second data
storage locations by placing on the second bus an address to which the
second particular one of said second storage locations is mapped and
receiving data via said second bus,

wherein one of said second plurality of bus masters connected to said
second bus caches data read out of a subset of said second data
storage locations, said second bus including means for conveying a
SNOOP signal with an address appearing on the bus, the SNOOP signal
telling said one of said second plurality of bus masters when to write
cached data to the address appearing on the bus,

the apparatus comprising: 

first mapping means coupled to said first bus for mapping first
addresses within the first address space to second addresses within
the second address space, for asserting an indicating signal and for
generating one of said second addresses in response to one of said
first addresses transmitted on said first bus from one of said first
plurality of bus masters, said first mapping means also generating a
SNOOP signal of a state indicating when a generated second address is
mapped to one of said particular subset of the second data storage
locations, and

bus interface means connected to said first and second buses for
responding to the first indicating signal when said one of said first
plurality of bus masters is reading data by placing the generated
second address and SNOOP signal on the second bus, receiving data from
a second data storage location mapped to said second address, and
transmitting the received data to said one of said first plurality of
bus masters via said first bus when the said one of said first
plurality of bus masters is reading data.
--------------
At its simpliest I would restate this as
There are two buses, first and second.  The second bus has the concept
of a SNOOP signal.  There is a bridge from the first to the second
bus.  When certain addresses are accessed on the first bus, the bridge
handles thoses accesses, maps them into corresponding addresses on the
second bus, and then acts like a bus master on the second bus (which
includes appropriately using the SNOOP signal).

So any system that bas a bus bridge where one of the buses implements
the concept of SNOOP would almost certainly have all of these
elements.

Hope that is helpful.

---

Request for Question Clarification by pafalafa-ga on 07 Oct 2005 19:51 PDT

Back again.

Thanks for the plain-English clarification.  I'm getting a clearer
picture of what's needed, and I think your original instincts were
right -- somewhere in the Futurebus protocol documents there probably
lies the description you're looking for.  However, none of the older
IEEE docs are accessible to me online -- I hope to find some other
means of accessing them.

Meantime, one more patent to consider, this one from 1987:


http://www.freepatentsonline.com/5142672.html


This doesn't have some of your key terms -- no mention of "snoop" for
instance.  Yet, it seems to be describing the mechanics of
communication and address error-checking between two busses.  This
seems (to my admittedly meager knowledge of the topic at hand) to be
functionally approaching the type of bus bridge/snoop system you're
asking about.

Anyway, it can't hurt to have a look, and I'd love to have your
feedback on it.  But I can understand if it gets a bit wearisome to
keep commenting on missed targets, so if I don't hear back, I'll just
keep plugging away...


paf

---

Clarification of Question by 704wil-ga on 08 Oct 2005 13:36 PDT

pafalafa-ga,

US5142672 describes a system that provides a bridge between two buses.
 However rather than mapping addresses in the 1st bus' address space
to the 2nd bus' address space, it teaches an automata consisting of a
set of registers whereby a actor on the 1st bus may specify an
operation on the 2nd.  Also I see no indication that the 2nd bus uses
the concept of a SNOOP signal. So it seems to be missing both of key
"teachings" of 5072369.

Hope that helps.

---

Request for Question Clarification by pafalafa-ga on 08 Oct 2005 14:07 PDT

Thanks for being so patient.

During the work week, I hope to able to get access to some old IEEE documents.

Mean time, I'm still going through worldwide patent literature.  I've
given up looking for anything with the term "snoop", and am instead
trying to zero in on the concepts.

For instance, here's some patent language going back to the 1970's:


=====
A memory module for use in a data processing system having a plurality
of memory modules and a memory address bus for transferring addresses
in said system, each said memory module comprising...

a main memory means operable at a first speed; 

an auxiliary memory means operable at a second speed higher than said
first speed for temporarily storing selected portions of the data
stored in said main memory means;

***associative memory means for temporarily storing selected main
memory addresses and comparing the stored addresses with an address
supplied from said memory address bus to said associative memory means
during a read or write operation to generate comparison data for
indicating whether data requested by said supplied address is stored
in said auxiliary memory means***

means for storing said selected data portions in said auxiliary memory
means so that the data stored in the auxiliary memory means of all of
said plurality of memory modules are arranged in an interleaved manner
such that data which are expected to be referenced sequentially during
the operation of said data processing system are sequentially stored
in the auxiliary memory means of different ones of said memory
modules.

=====


The paragraph with the *** sounds to me a lot like a bridge for mapped
addresses and a snooping scheme.  Not 100% percent, perhaps, but a
good chunk of them, anyway.

However, I've been missing the mark on the others, so I don't want to
go too far down this path without checking in with you.

As long as you're amenable to my doing this, I'll keep hunting things
down and running them by you.  If it's getting to be an annoyance,
though, let me know, and I'll take another tack.

Thanks,

paf

---

Clarification of Question by 704wil-ga on 08 Oct 2005 19:01 PDT

pafalafa-ga,

My reading of this excerpt is that the "associative memory means" is
what we now commonly call a "cache".  Not relevant I think.

---

Request for Question Clarification by pafalafa-ga on 17 Oct 2005 09:03 PDT

Still hunting...!

Does this sound anywhere near the target?


=====
In a typical CISC CPU, on-board memory is dual-ported to allow access
by the on-board processor as well as by other masters on the system
bus. In this RISC CPU, on the other hand, the on-board memory is
single-ported but shared among various resources by means of a
dedicated memory bus with its own full-blown priority arbitration
scheme.

"Since the 88100 executes to a large extent directly out of cache, it
doesn't have to rely on the board's local bus or dynamic RAM for
instructions except on cache misses, so why not let the local bus be
used for something else?" notes Andreas Schreyer, RISC product
marketing manager.

In the boards, the bust-snooping [sic] logic that's a part of the
88200 cache memory-management units is used to maintain cache
coherency. "If we used dual-port memory," explains Schreyer, "and,
say, a disk controller performs a DMA transfer into the memory, this
would be hidden from the 88200 and the cached data would be stale.
With the bus-snooping circuitry continuously observing M bus traffic
and detecting when a cached memory location is being modified, the
appropriate cache entries will be invalidated."
=====

The article is dated Nov 1988.


Let me know what you think.


paf

---

Clarification of Question by 704wil-ga on 17 Oct 2005 15:08 PDT

pafalafa-ga,

The Motorola 88000 series used bus snooping functionality on their
bus.  So such a system could be the basis of the second bus in our
desired art.  But, of course, the other elements are still necessary.