A data processor for execution of tagged data and tagless data has a decoder for discriminating whether the data is tagged or tagless one and in case of a tagged data, separates a tag part and uses the remaining part for address computation. The data processor also comprises a unit for evaluating the tag part and a micro program controller for multi-branching in accordance with the evaluation result of the tag part. The tag evaluating unit includes an extender eliminating part for extracting the tag part from data on a data bus, a plurality of tag part storing registers for storing the tag part from the eliminating part under the control of the micro program controller, and a tag multi-way jump encoder for generating a tag multi-way jump address to feed it to the controller on the basis of the outputs of the registers and a signal from the micro program controller, thereby enabling tag multi-way jump.

In a data processing system a cache memory comprises level one and level two even and odd data stores and level one and level two even and odd directory stores. The directory stores include a plurality of storage locations for storing the most significant bits of the address numbers associated with the data words stored in the level one and level two even and odd data stores. The level one and level two even and odd directory stores are addressed by the least significant bits of the address numbers. Comparator circuits compare the high order bits of an address number supplied in a memory request to the high order bits stored in the level one even and odd directory stores at storage locations identified by both the low order bits of the address supplied in the memory request and the low order address bits incremented by one. A hit detector circuit determines whether one, both, or none of the requested words are stored in the cache memory by analyzing the outputs of the comparators.

A memory system includes a high-speed, multi-region instruction cache, each region of which stores a variable number of instructions received from a main data memory said instructions forming part of a program. An instruction is transferred to a region from the main data memory in response to a program address and may be executed without waiting for simultaneous transfer of a large block or number of instructions. Meanwhile, instructions at consecutively subsequent addresses in the main data memory are transferred to the same region for building an expanding cache of rapidly accessible instructions. The expansion of a given region is brought about as a result of the addressing of that region, such that a cache region receiving a main line of the aforementioned program will be expanded in preference to a region receiving an occasionally used sub-routine. When a new program address is presented, a simultaneous comparison is made with pointers which are provided to be indicative of addresses of instructions currently stored in the various cache regions, and stored information is gated from a region which produces a favorable comparison. When a new address is presented to which no cache region is responsive, the least recently used region, that is the region that has been accessed least recently, is immediately invalidated and reused by writing thereover, starting with the new address to which no cache region was responsive, for accumulating a substituted cache of information from the main data memory.