Abstract:
Apparatus and process for the rapid processing of the data in a data processing system having a segmented memory, wherein descriptors representing the characteristics of the segments are employed in retrieving from memory and processing each segment, and wherein means is provided for the rapid locating of the descriptors for the segments most frequently utilized.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to an apparatus and a process for the rapid processing of segmented data. 
     In prior art data processing systems segmenting of the memories, the central processor memory, as well as the auxiliary memories, has been implemented by assigning an identification number to each memory segment and by storing the characteristics of each segment (address, length, access rights, etc.) termed &#34;segment descriptor&#34; in a particular register. The set of these descriptors constitutes a general table of segment descriptors. This arrangement has the advantage of simplifying the task of the programmer for whom the central processor memory and the auxiliary memories then form a unit which may be considered as a single memory. 
     In a system organized in this manner, when the address calculating mechanism furnishes the identification number of a segment, the corresponding descriptor must be located in the general table in order to provide for controlling the access rights, verifying if the length of the segment is sufficient for the capacity demanded by the program, and locating such segment by the address held in the descriptor. 
     When the capacity of the memory unit is very large, the number of segments and, therefore, of descriptors is very large. In such instance the selection of a descriptor from the general table is performed by an approach termed &#34;hierarchizing&#34;, which increases considerably the time for locating a descriptor. The preformance of such systems is therefore limited. 
     Accordingly, it is the object of this invention to reduce the time for selecting segment descriptors in a data processing system having segmented memories. 
     Another object of this invention is to increase the preformance of a data processing system having segmented memories. 
     SUMMARY OF THE INVENTION 
     The apparatus of the present invention providing for the rapid processing of segmented data is applicable to a data processing system, wherein the memory unit is divided into m addressable segments, each segment being assigned an identification number, wherein the characteristics of each segment are stored in a respective segment descriptor forming part of a general descriptor table, and wherein the descriptors are adapted to be called successively, in any order, by means of an address calculating device placed under control of a supervisory program. The invention is principally characterized by comprising essentially an auxiliary table unit, having evolving contents, for n descriptors, n being relatively small compared to m, and a control unit, having evolving contents, and having two banks of indicators. The two banks consist of a bank of presence indicators for validating the use of the n descriptors contained in the auxiliary table unit at any moment in the processing of the supervisory program and a bank of reference indicators for identifying, among others, the last A different segments called. These last a different segments are called during the addressing, which addressing may be represented as of rank (np) + A of the supervisory program (A being less than or equal to n and p being greater than or equal to 1). The invention also comprises an enabling unit for steering the entry of the descriptors into the auxiliary table unit under control of the contents of the control unit, and a transfer network between, on one hand, the auxiliary table unit, the control unit and the enabling unit, and, on the other hand, the processing unit of the system, such transfer network being enabled by commands emitted in sequence by the command unit of such processing unit. 
     In accordance with the invention, the supervisory process of the claimed apparatus is pricipally characterized by comprising essentially the steps of: defining a number n of segment calls which is small in relation to m and which has a value approaching the frequency of repetition of the calls made in the course of a program to the first segments called at the start of such program; and storing the descriptors of the segments called in an auxiliary table unit of n descriptor registers by orienting the evolution of such table according to two phases: 
     a first phase, termed the loading phase, in the course of which the storing of the descriptors of the n first different segments called is made in the registers of rank 1 to n of the auxiliary table unit respectively; and, 
     a second phase, termed the replacement phase, during which each segment called (a) causes the &#34;marking&#34; of the corresponding descriptor of the auxiliary table unit if it is present in such table, and (b) causes the replacement by the corresponding descriptor of the first descriptor not &#34;marked&#34; counting from register n if such corresponding descriptor is not present in the auxiliary table unit. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention will be described with reference to the accompanying drawing, wherein: 
     FIG. 1 is a block diagram of the components comprising the apparatus of the invention; 
     FIGS. 2, 3A, 3B, 4A and 4B are block diagrams, in more detail, of the components shown in FIG. 1; and 
     FIG. 5 is a flow chart of the process of the invention which exploits the capabilities of the apparatus realized in accordance with the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The diagram of FIG. 1 comprises three blocks, wherein: 
     block 2 represents the processor UEX of the system and its command unit UCM, 
     block 4 represents an auxiliary table unit UTA and a control unit UCT of the apparatus of the invention, and 
     block 3 represents an enabling unit UV and a transfer network RT of the apparatus. 
     As is known, command unit UCM delivers orders &#34;O&#34; in sequence; however, according to the results obtained from the execution of these orders, the sequence may undergo branching to another sequence (symbolized by the connection os in FIG. 1). 
     Auxiliary table unit UTA comprises two banks of registers; namely, a descriptor register bank RRD providing for the storage of n descriptors (which have been described previously herein) and an identifier register bank RRS providing for the storage of the identification numbers of the segments whose characteristics are contained in the n descriptors stored at each moment of the process. 
     Control unit UCT comprises two banks; namely, a presence indicator bank RIP which, as mentioned previously herein, validates the use of the n descriptors loaded into bank RRD during the course of a process, and a reference indicator bank RIR which provides for identifying the last A different segments called during the course of an addressing, which addressing may be represented as of rank (np) + A. The connection of control unit UCT with enabling unit UV provides for the evolution of the contents of descriptor register bank RRD. 
     The connections t symbolize the information transfers and the connections ud symbolize the enabling signals transferred. 
     FIG. 2 represents, in more detail, the processor UEX shown in FIG. 1. Only certain components of processor UEX have been represented in FIG. 2. Command unit UCM, as is known, comprises two fixed memory blocks MCO and MCl. Command unit UCM, after receiving a starting pulse D, delivers in sequence orders &#34;O&#34; issuing from one or the other of memory blocks MCO or MCl. The choice of the order to be delivered by command unit UCM, from between the two orders issuing, is made through the intermediary of a circuit (not shown) controlled by either the signal v or the signal v. This arrangement enables branching of the sequence of the orders. The sequence of orders which define the process of the invention may undergo three branchings (controlled by signal groups v1-v1, v2-v2 and v3-v3). 
     Processor UEX also comprises a general table of descriptors TG which, when it receives a segment identification number rtg, delivers the corresponding descriptor dtg, which holds the characteristics of the segment. 
     FIG. 2 also shows that processor UEX comprises a source of information signals nsr which represent the identification numbers N of the segments to which there must be successive access during a process. These segment mumbers N are furnished by the address calculating mechanism. 
     FIG. 4B represents auxiliary table unit UTA which, as has been mentioned previously herein, comprises a descriptor register bank RRD and an identifier register bank RRS. 
     FIG. 4A represents control unit UCT which comprises a presence indicator bank RIP and a reference indicator bank RIR. 
     Descriptor register bank RRD, FIG. 4B, primarily comprises n registers D1-Dn. Each register of bank RRD (which, during the process, contains the characteristics of the segment to which it is temporarily assigned) is associated with: 
     one of registers S1-Sn of bank RRS (registers S1-Sn contain the identification numbers of the related segments), 
     one of presence indicators P1-Pn of bank RIP, and 
     one of reference indicators R1-Rn of bank RIR. 
     The descriptor contents cdv of a descriptor register, for example register D1, are delivered to the process through an AND-gate (without reference numeral, but illustrated immediately to the right of the corresponding one of registers D1-Dn), which is enabled by the condition signal clv initiated by a comparator C1. Each of registers S1-Sn is associated with one of comparators C1-Cn. When the information cns (representing a segment identification number) that is delivered simultaneously to the n comparators C1-Cn is identical to the contents of one of the identifier registers, for example, register S1, the corresponding comparator Ci delivers a signal ci representing a match, for example, comparator C1 delivers the condition signal c1. However, the condition signal clv, which is initiated as a result of the generation of condition signal c1, is only delivered by an AND-gate (without reference numeral, but illustrated immediately above the comparator C1) when the gate is enabled by a condition signal p11. Condition signal p11 is supplied by presence indicator P1. 
     Each presence indicator and each reference indicator, FIG. 4A, can be operative in one or the other of two states representing respectively the binary numbers 1 and 0. The state in which each of these indicators is operating is represented by the presence of one or the other of two condition signals on the output leads of the indicators (for example, the signals p11 and p10 for indicator p1). The indicators enter into one or the other of their two states under the control of respective signals (for example, for indicator p1, the signal 1p1 and the signal delivered by the order &#34;ROP&#34;). It is to be noted that the order &#34;ROP&#34; resets the n presence indicators to the state 0, and similarly, that the order &#34;ROR&#34; resets the n reference indicators to the state 0. 
     The operation of the apparatus of the invention and the supervisory process claimed for such apparatus will now be explained by reference to FIGS. 2, 3A, 3B, 4A, 4B, and to the control flow chart of FIG. 5. 
     The starting pulse D furnished by processor UEX triggers the starting of command unit UCM, FIG. 2, which supplies at the beginning two first order; namely, the order &#34;ROP&#34; which resets all of presence indicators P1-Pn to the state 0, and the order &#34;ROR&#34; which resets all of reference indicators R1-Rn to the state 0. 
     The next order &#34;TNR&#34; enables the transfer of the identification number N of the first segment called by the program into a waiting register RN (FIGS. 2 and 3A). 
     The next order is a comparison order &#34;CNS&#34; for comparing the segment identification contents (rn) of register RN with the segment identification number contents of each of the registers of identifier register bank RRS. In effect, the order &#34;CNS&#34; enables the transfer of the contents of register RN (FIG. 3A) in parallel to one set of input leads of each of comparators C1-Cn. At this stage in the execution of the program, even if one of the registers S1-Sn contains the identification number of the segment called, the AND-gates (without reference numerals, but illustrated immediately above comparators C1-Cn) associated with comparators C1-Cn are not enabled to transfer any of the signals c1-cn because the condition signals p11-pn1 are not present, so that no descriptor can be furnished to the process (FIG. 4B). The order &#34;CNS&#34; is also applied to a network of AND-gates (lower right portion of FIG. 3A), which at this time are enabled by the condition signals p10-pn0, causing issuance of the condition signal v1. Signal v1 is delivered to command unit UCM (&#34;NO&#34;, in flow chart of FIG. 5), causing the sequence of the commands to branch to a search of general descriptor table TG. 
     The ensuing search order &#34;RTG&#34; causes the transfer, FIG. 3A, into general descriptor table TG of the segment identification number held in register RN (in form of information signals rtg). The corresponding descriptor contents of table TG are transferred, as information signals dtg, into a process register EX (FIG. 3A). 
     The next order &#34;TEP&#34; is an order for testing the state of presence indicator bank RIP. If all of presence indicators P1-Pn are in state 1, the order &#34;TEP&#34; leads to the generation (lower central portion of FIG. 3A) of the condition signal v2 (&#34;YES&#34;, in flow chart of FIG. 5). On the other hand, if any one of the presence indicators is in state 0, the order &#34;TEP&#34; leads to the generation of the condition signal v2 (&#34;NO&#34;, in flow chart of FIG. 5), which is the situation at the stage of the program presently being described. Condition signal v2 causes the sequence of commands to branch to a loading phase for auxiliary table unit UTA. 
     The nodes of the subsequent loading phase are determined by the next order &#34;CPA&#34; and the network I of AND-gates of enabling unit UV, FIG. 3B. The segment identification number, represented by information signals rn, and the corresponding descriptor, represented by information signals ex, of the first segment called are loaded into respective registers S1 and D1 of auxiliary table unit UTA by means of AND-gates (without reference numerals, but illustrated immediately to the left of registers S1 and D1) enabled by a condition signal al, FIG. 4B. Condition signal al is generated when the order &#34;CPA&#34; is applied to the input lead of network I, and network I is at that time enabled by condition signal p10, FIG. 3B, It is to be noted, FIG. 4A, that simultaneously condition signal al sets both presence indicator P1 and reference indicator R1 to state 1. 
     This process is repeated identically for the n first segments called, except that for the second segment, the order &#34;CPA&#34; results in the loading of registers S2 and D2 of auxiliary table unit UTA. Registers S2 and D2 are loaded through the direction of AND-gates of network I which are enabled by condition signals p11 and p20, etc. The last of the n first segments has its identification number and its descriptor loaded into respective registers Sn and Dn. 
     In the ensuing program, if the descriptor of a segment called is found to be in auxiliary table unit UTA, such descriptor will be retrieved directly therefrom, because the corresponding presence indicator is found to be in state 1. The presence of the corresponding one of the presence indicator output signals p11-pn1 enables transfer of the corresponding one of comparator output signals c1-cn, FIG. 4B, issuing as a result of the segment number comparison controlled by the order &#34;CNS&#34;. The correspondingly generated one of signals c1v-cnv thereupon enables the contents of the corresponding one of descriptor registers D1-Dn to be transferred, as information signals cdv, into process register EX, FIG. 3A. The one of condition signals c1v-cnv that enables the transfer of the corresponding descriptor to register Ex, also sets the corresponding one of reference indicators R1-Rn to state 1 (the reasons for this arrangement appearing hereinafter in this description). The order &#34;CNS&#34;, which is also applied to the AND-gate network shown in the lower right portion of FIG. 3A, causes issuance of the condition signal v1 (&#34;YES&#34;, in the flow chart of FIG. 5), by virtue of the AND-gate of such network that is enabled by one of the condition signals clv-cnv supplied thereto. 
     However, if in the ensuing program, the order &#34;CNS&#34; generates the information that the descriptor of a segment called is not found to be in auxiliary table unit UTA, as described previously herein, the sequence will be caused to branch to a search of general descriptor table TG. In this instance, the condition signals c1-cn provide for the generation of condition signal v1, FIG. 3A. 
     The order &#34;TEP&#34;, which follows the retrieval of a descriptor from table TG, leads to generation of the condition signal v2 when all of presence indicators P1-Pn are in state 1, FIG. 3A, whereupon the sequence will be caused to branch to a phase for replacing a descriptor. 
     The descriptor replacement phase starts with a test order &#34;TER&#34;, which order tests the state of reference indicators R1-Rn. If any one of indicators R1-Rn is in state 0 (lower left portion of FIG. 3A), the condition signal v3 issues (&#34;NO&#34;, in flow chart of FIG. 5), whereupon the sequence will be caused to branch directly to the descriptor replacement. If all of reference indicators R1-Rn are in state 1, the condition signal v3 issues (&#34;YES&#34;, in flow chart of FIG. 5), whereupon the sequence will be caused to branch to the order &#34;ROR&#34; (resetting all reference indicators to the state 0) prior to the descriptor replacement. 
     The modes of the replacement phase are determined by the next order &#34;CPB&#34; and the network II of AND-gates of enabling unit UV, FIG. 3B. Two cases will be considered: 
     First case: The order &#34;ROR&#34; has been generated immediately prior to the replacement and all of the reference indicators R1-Rn are in state 0. The identification number and the descriptor of the new segment called will be loaded into registers Sn and Dn of auxiliary table unit UTA through AND-gates enabled by a condition signal bn (the order &#34;CPB&#34; applied to network II, which is at that time enabled by condition signal rn0, provided by indicator Rn being in state 0, causes generation of signal bn, FIG. 3B). 
     Second Case: The order &#34;ROR&#34; has been generated during an earlier replacement phase and it is assumed that afterwards the segment, whose identification number and descriptor had been initially loaded into registers Sn and Dn, has been called (it has been shown in the preceding description that the direct use of the contents of a descriptor register is accompanied by maintaining in or setting to state 1 the corresponding reference indicator). The identification number and the descriptor of the new segment called may now be loaded into registers S(n-1) and D(n-1), (the order &#34;CPB&#34; applied to network II, FIG. 3B, which is at that time enabled by condition signals rn1 and r(n-1)0, causes generation of signal b(n-1)). 
     If the operation of the apparatus and process which have been described above are generalized, the following principle may be expressed: 
     that auxiliary table unit UTA is loaded initially with the descriptors of the first n different segments called; 
     that each new different segment called gives rise to the storing of its corresponding descriptor in auxiliary table unit UTA and that the modes of descriptor replacement which are imposed are managed according to a separate rule. Thus, the process utilized can be defined as two phases: 
     a first phase, the aforementioned loading phase, during which the descriptors of the first n different segments called are loaded in order into respective registers of rank 1 through n of auxiliary table unit UTA; 
     a second phase, the aforementioned replacement phase, during which each segment called (a) causes the &#34;marking&#34; of its corresponding descriptor in auxiliary table unit UTA if such descriptor is found present in unit UTA, and (b) causes the replacement with its corresponding descriptor of the first descriptor in unit UTA not &#34;marked&#34; counting from descriptor register n through 1 if such corresponding descriptor is not found present in unit UTA. 
     This apparatus takes into account a certain number of observations which include, among others: that the first segments called at the beginning of a program have the tendency to be utilized with relatively regular frequency; and during the course of the program, the segments which are the most recently called have the tendency to be called immediately thereafter. 
     Therefore, these observations were among reasons for establishing a procedure such as described herein in which, in the loading phase, descriptors are loaded in order into registers D1 through Dn of the auxiliary table unit, and in the replacement phase, descriptors are entered in the opposite sense; i.e., descriptors are replaced starting from register Dn. The number n may be the result of a compromise between the variations of the frequency of utilization of the first segments called and the lowest value that it must have relative to m in order to justify the cost of the apparatus. 
     In practice, the apparatus and the process of the invention applied to a data processing system have led to selecting the number 8 for the number of descriptor registers in the auxiliary table unit. The time of searching for the descriptors is thereupon reduced by 13 to 1. 
     It is to be understood that the preceding description has been made by reference to a single nonlimiting example and that the variations of the invention may be directed especially to: the number of descriptor registers of the auxiliary table unit; the mode of controlling the apparatus; the possibility of preventing the replacement of a particular descriptor the concept of the reference indicators (which can make allowance for the frequency of use of the segments whose descriptors are held in the auxiliary table unit); the embodiment of the presence and reference indicators (which may be constituted of registers having n positions); and/or the possibility of replacing a descriptor of rank i, wherein 1 ≦ ≦ n, by simultaneously resetting to state 0 indicators Pi and Ri; all of which may be implemented without departing from the heart of the invention.