Computer Memory Address Matcher and Process

The invention pertains to computer and data processing systems in general and, in particular, to utility circuits which are a part of, or attached to, such systems and to utility processes for aiding the debugging of programs.

It has been a common practice for companies involved in the development of computer systems and software also to provide a separate utility system having the ability to monitor internal computer operations. Typically, such utility systems are used by programmers to "snap" internal computer and memory states at selected points of program operation. These points may be identified, for example, by the execution of program instructions or read/write operations at particular computer memory addresses or blocks of addresses. For example, one typical utility circuit is a block address matcher used to detect transactions at computer memory addresses within a range, or block, defined by specified upper and lower boundary addresses. The circuitry required to implement these utility systems has been traditionally large because of the technology involved. This was not a significant problem in the past, however, because the utility systems were generally used by system designers for noncommercial laboratory use only.

With the advent of modern large-scale integrated circuits resulting in smaller and smaller computer systems and the recognition that the software of complex computing systems is never completely debugged, it is becoming desirable to include utility debugging packages as integral system parts for field debugging. Since utility packages have no role in the normal functional operation of computing systems, it is essential that the physical space occupied by such a package be as small as possible. Even with the use of large-scale integrated circuits in the utility packages, the circuit space required using conventional techniques may be objectionable in comparison to the space occupied by a computer. For example, one conventional technique of implementing computer memory block address matchers in a utility package is to wire in cascade a sufficient number of magnitude comparators to account for each address bit of a computer memory addressing structure. For a 24-bit address bus, for example, a block address matcher using this conventional technique would require six 8-bit buffers for storing an upper and a lower block address for the memory block to be monitored; six 4-bit comparators for each of the upper and lower block addresses, plus some incidental output logic. This amounts to about 18 or 19 integrated circuit chips requiring housing space on the order of perhaps three circuit packs. It would be highly desirable to reduce this space requirement to no more than one circuit pack, especially if the circuitry is to be an integral part of a computer. Related goals would be to accomplish this with circuitry that is less expensive and more conservative of power than conventional techniques.

The above problems are solved and an advance in the art is obtained in an address matcher and process therefor for detecting computer address transactions occurring within a block of consecutive addressess. The matcher comprises a plurality of memories, each of which is addressable by a different prescribed subfield of the computer address field being monitored. Each addressable location of each memory contains encoded data which defines an in-block or out-of-block condition for that subfield of the computer address with which it is associated. Matcher output circuitry is responsive to the encoded data read from each of the memories as a result of a monitored address transaction for decoding the data to determine if the monitored address lies within the specified address block.

In the preferred embodiment the matcher is used to monitor computer memory address transactions such as instruction fetches and read or write operations. The matcher memories are implemented by three random access memory (RAM) integrated circuit (IC) chips each having 256 words (addressable locations) by 4 bits per word. The computer and computer memory in this embodiment use a 24-bit address bus (field). Each RAM is addressed by a different 8-bit subaddress (subfield) of the computer memory address bus. Two embodiments of output circuitry which decode data from the RAMs is disclosed. The first embodiment uses two 4-bit adders. This embodiment is preferred because it is slightly faster in operation than the second embodiment which uses two 4-bit magnitude comparators.

Write access to the RAMs is provided so that any computer memory address block to be monitored may be specified at will. The data written into the RAMs is encoded to define the monitored block and eliminates the need for separate buffers to store upper and lower block addresses as required in the prior art. The preferred illustrative embodiment thus comprises only three RAM IC chips and two output circuit IC chips as compared to the 19 chips in the mentioned prior art example.

In the drawing:

FIG. 1 illustrates in block diagram form a computing system including a memory whose address transactions are to be monitored and a computer containing a block address matcher for monitoring address transactions of the memory;

FIG. 2 discloses the circuit details of one embodiment of the address matcher which uses RAM chips for the matcher memories and integrated circuit adders for the matcher output circuitry;

FIG. 3 illustrates the encoded data that would be programmed into the matcher memories of FIG. 2 for an illustrative computer memory block to be monitored;

FIG. 4 discloses another embodiment of the output circuitry of the matcher which uses integrated circuit magnitude comparators for the output circuitry; and

FIG. 5 illustrates the encoded data that would be programmed into the matcher memories for an illustrative computer memory block in the embodiment of the invention shown in FIG. 4.

In accordance with the preferred embodiment of the invention, FIG. 1 illustrates a computer system including a memory 10 and a computer 11. Computer 11 illustratively includes a block address matcher 12 as an integral part of its circuitry. Transactions between memory 10 and computer 11 occur over a read/write bus 14 at memory address locations specified on address bus 13. Computer memory address register 15 supplies memory addresses on the leads of bus 13 for this purpose.

Matcher 12 monitors address transactions of computer 11 with memory 10 by means of leads 17 connecting to address bus 13 and generates a match signal on an output lead 16 whenever a memory address falls within a prescribed block of consecutive addresses. As will be seen, matcher 12 contains a plurality of matcher memories, each of which contain encoded data which define the computer memory addresses of the block to be monitored. An internal data bus 20 connects matcher 12 to a data register 21 by means of which data may be inputted into matcher 12 to define the address block to be monitored. The match signal occurring on lead 16 whenever computer 11 addresses a location in memory 10 contained within a monitored block may be used in any desired manner to indicate an address transaction occurring within the block. The match signal, for example, could be used to trigger a computer 11 interrupt which might result in the "snapping" of the internal state of the computer or of specified areas of memory 10. Alternatively, the match signal could activate additional hardware (not shown) to effect a "snap" without affecting the program flow of the computer.

FIG. 2 illustrates the preferred embodiment of block address matcher 12. The matcher comprises a plurality of random access memories (RAMs) 30, 31, and 32 and two adders 34 and 35. Each of the RAMs is illustratively a Fairchild 93412 integrated circuit forming an array of 256 words, or rows, by 4 bits per word in this embodiment. The adders 34 and 35 are conventional full adders capable of adding two 4-bit binary numbers A.sub.4 A.sub.3 A.sub.2 A.sub.1 and B.sub.4 B.sub.3 B.sub.2 B.sub.1, where A.sub.4 and B.sub.4 are the most significant digits. These binary designations are chosen to correspond to the input terminal designations of the adders shown in FIG. 2. In addition, each adder has an input "carry" terminal C0 and an output "carry" terminal C4.

By way of example, memory address bus 13 of FIG. 1 contains 24 address leads ADDR0-ADDR23 shown in FIG. 2, together with a number of mode control leads MO1, MO2 and MO3 discussed further below. Each of the RAMs 30, 31, and 32 is addressed by a different subfield of the memory address bus leads; specifically and illustratively, RAM 30 is addressed by the eight lower order leads ADDR0-ADDR7, RAM 31 is addressed by the eight middle order leads ADDR8-ADDR15, and RAM 32 is addressed by the eight upper order leads ADDR16-ADDR23. Each RAM has four input data terminals D1-D4 and four output data terminals 01-04. These terminal designations are shown on RAM 30 and omitted on RAMs 31 and 32 for simplicity. The input terminals D1 through D4 are attached to designated leads of internal data bus 20 shown in FIG. 1 so that the RAMs may be programmed with encoded data. For example, the input data terminals of RAM 30 are connected to data bus leads ID1 through ID4. The output terminals 01 through 04 are connected to prescribed inputs of adders 34 and 35 by means of leads 0D1 through 0D12. The output data leads are also connected to their associated input data leads by means of connections 33 to provide for both read and write access of the RAMs by computer 11. Thus, leads 0D1 through 0D4 are connected to leads ID1 through ID4, respectively. Connections 33 are shown only on RAM 30 for simplicity. However, it is understood that leads 0D5 through 0D12 associated with RAMs 31 and 32 are also connected to leads ID5 through ID12, respectively.

Mode control leads MO1, MO2, and MO3 are illustratively part of the memory address bus 13 and are used to control the operations of each of the RAMs. Lead MO1, for example, is connected to chip select terminal CS2 of each of the RAMs (not shown on RAMs 31 and 32) and a signal thereon activates the RAMs whenever data is to be written into or read from the RAMs. Chip select terminal CS1 is grounded on each of the RAMs. A control signal on lead MO2 places each of the RAMs into a read mode when the RAMs are activated. A signal on lead MO3 places each of the RAMs into a write mode.

Each word of each RAM contains four bits. Two of the bits are associated with an upper block address and two of the bits are associated with a lower block address. The upper address bits appear on RAM output leads 0D1, 0D2, 0D5, 0D6, 0D9 and 0D10 and are routed to adder 34. The lower address bits appear on RAM output leads 0D3, 0D4, 0D7, 0D8, 0D11 and 0D12 and are routed to adder 35. One bit of each word associated with the upper block address is programmed to a binary "1" if the RAM address of that word is less than the state of the corresponding subfield of the upper block address. The other bit of each word associated with the upper block address is programmed to a binary "1" if its RAM address is less than or equal to the state of the corresponding subfield of the upper block address. Otherwise, these bits are programmed to binary "0". These two bits of each word thus satisfy the following truth table where <U means "less than the upper block address" and .ltoreq.U means "less than or equal to the upper block address":

RAM 32 is associated with the most significant computer memory address subfield ADDR16-ADDR23. The two upper block address bits when read from RAM 32 as a result of a computer memory transaction are added in the most significant stage A4, B4 of adder 34. Thus, adder 34 generates a "carry" signal at C4 if the ADDR16-ADDR23 subfield of the computer memory address which addresses RAM 32 is less than (<U=1; .ltoreq.U=1) the corresponding subfield of the upper block address. If the ADDR16-ADDR23 subfield is greater than the corresponding subfield of the upper block address (<U=0; .ltoreq.U=0), adder 34 cannot produce a "carry" at C4. If the ADDR16-ADDR23 subfield is equal to the corresponding subfield of the upper block address (<U=0; .ltoreq.U=1), whether or not a "carry" signal is produced at C4 is determined by the next most significant stage A3, B3 of adder 34. This stage operates exactly as described above with respect to the <U, .ltoreq.U bits read from RAM 31, as does the next most significant stage A2, B2 which controls the generation of a C4 "carry" in the event the A3, B3 stage is unable to resolve the decision. The least significant stage A0, B0 and the cascade "carry" input C0 are connected to a potential 36 so that this stage always generates an internal "carry" to stage A2, B2. This causes an internal "carry" to be propagated through each stage to the C4 output when the computer memory address equals the upper block address.

Adder 35 operates in a similar fashion as adder 34 with respect to the two bits from each of the RAMs associated with a lower block address. These bits are designated as >L and .gtoreq.L and are programmed to a binary "1" if the subfield of the computer memory address by which they are addressed satisfies the criteria of being "greater than" (>L) or "greater than or equal to" (.gtoreq.L) the corresponding part of the lower block address. Thus, adder 35 produces a "carry" signal at its C4 output in response to a computer memory transaction if the computer memory address is "greater than or equal" to the lower block address.

The C4 "carry" signals are combined by NAND gate 37 which produces a low going signal on match signal lead 16 if the computer memory address is both equal to or less than the upper block address and equal to or greater than the lower block address.

FIG. 3 shows the contents of RAMs 30, 31 and 32 for an illustrative example in which the upper block address is 030201.sub.16 and the lower block address is 010203.sub.16. These addresses are specified here in base 16 because two digits in base 16 produce 256 addresses for a one-to-one correspondence with the 256 words of each of the RAMs. Thus, the most significant digits 03 and 01 of the illustrative upper and lower addresses, respectively, define the block range in RAM 32, the middle digits 02 and 02 of the upper and lower addresses, respectively, define the range in RAM 31, and the least significant digits 01 and 03 of the upper and lower addresses, respectively, define the block range for RAM 30. A brief examination of FIG. 3 should clarify the above discussion. Referring to the contents of RAM 32, for example, since the most significant subfield of the upper block address is 03, each <U bit in words 0, 1 and 2 is set to "1"; this bit is set to "0" in all other words. The .ltoreq.U bits in words 0 through 3 are set to "1" and all other .ltoreq.U bits are set to "0". Similarly, since the most significant subfield of the lower block address is 01, all >L bits in RAM 32 are set to "1" with the exception of the bits in words 0 and 1. All the .gtoreq.L bits are set to "1" with the sole exception of this bit in word 0. The bits in RAMs 31 and 30 are established in a similar fashion with reference to the subfields with which they are associated.

FIG. 4 illustrates an embodiment of the address matcher in which adders 34 and 35 of FIG. 2 have been replaced with magnitude comparators 40 and 41, respectively. By way of example, these comparators are Texas Instruments, Inc., Type SN 74S85 four bit comparators. Comparator 40 operates on bits from RAMs 30, 31 and 32 associated with the upper block address. Comparator 41 operates on lower block address bits. Both comparators compare the binary values on the B terminals B3, B2, B1 to that on the respective A terminals A3, A2, A1 and produce an appropriate signal on its A>B OUT terminal. The cascade input terminals A>B IN, A=B IN and A<B IN of both comparators are grounded. The SN 74S85 comparator as wired in this embodiment and in conjunction with the coding of the matched RAMs as described below produces an output signal on its A>B OUT terminal whenever the magnitude of the A number is greater than or equal to the magnitude of the B number. The A>B OUT signals are combined by NAND gate 37 to generate match signal 16.

The RAMs are programmed differently for the magnitude comparator embodiment. FIG. 5 illustrates the contents of the RAMs for this embodiment for the same illustrative block addresses used in FIG. 3. As seen, each RAM has .ltoreq.U (less than or equal) and .gtoreq.U (greater than or equal) bits for the upper block address, and .gtoreq.L and .ltoreq.L bits for the lower block address. Thus, referring to the contents of RAM 32 in FIG. 5, for example, because the corresponding upper address subfield is 03, the .ltoreq.U bits of words 0 through 3 are set to "1" and the remaining .ltoreq.U bits are "0"; the .gtoreq.U bits of all words are "1" excluding words 0 through 2 which are "0". Because the corresponding subfield of the lower block address is 01, the .gtoreq.L bits of all words except word 0 are set to "1" and the .ltoreq.L bits in only words 0 and 1 are set to "1".

The arrangement above operates to produce signals from both magnitude comparators 40 and 41 on their A>B OUT terminals whenever the address on a computer memory transaction is less than or equal to a specified upper block address and greater than or equal to a lower block address. If both output signals are present, NAND gate 16 generates a signal on match signal lead 16.

In view of the above teaching, it is obvious that either block matcher can be used as a single address matcher by merely treating the computer memory address in question as both the upper and lower block addresses and programming the RAMs as described above for either embodiment.

Other conditions can, of course, be included as criteria for generating the match signal 16. For example, output circuitry could be added which would allow the generation of output signal 16 only if a data read operation, for example, were occurring. Other output circuitry could be added to require a match of the data being written or read on the read/write bus 14 as an additional criterion.

It is to be understood that the above-described arrangement is merely illustrative of the application of the principles of the invention and that other arrangements may be devised by those skilled in the art without departing from the spirit and scope of the invention.