Reducing inherited logical to physical register mapping information between tasks in multithread system using register group identifier

[0002] 1. Field of the Invention

[0003] The present invention relates generally to a register content inheriting system in a multi-processor. More particularly, the invention relates to a multithread microprocessor executing a plurality of instructions simultaneously.

[0004] 2. Description of the Related Art

[0005] As a technology for speeding-up a program, there has been proposed a system for performing a parallel processing through a thread by dividing the program into a plurality of threads. Adapting to such thread level parallel processing, study for the processors have been progressed. The thread level parallel processing system takes a method to improve a processing speed with improving use efficiency of an arithmetic unit by executing a plurality of threads simultaneously instead of parallel characteristics of the instruction unit.

[0006] Such thread level parallel processing can be classified to one no dependency between the threads with each other for some problems to be solved at all, one having low dependency and whereby having less problem in performance even when dependency is resolved by a software and one having high dependency and thus requiring execution aid of thread level parallel processing by hardware.

[0007] When there is no dependency between the threads or when dependency between threads is low and thread is large, gain by parallel processing may be higher than an overhead of thread management by a software. Therefore, a support in a hardware can be restricted to be minimum.

[0008] However, in certain problem to be solved, dependency can become high or thread per se becomes small, some hardware support becomes necessary.

[0009] Upon speeding up of fine thread, efficient thread generation and data transfer between the threads are inherent. For example, as one example of a parallel processing multi-processor of fine threads has been disclosed “Multiscalar Processor (Gurinder S. Sohi, Scott E. Breach and T. N. Vijaykumar, The 22ns International Symposium on Computer Architecture, IEEE Computer Society Press, 1995, pp 414-425.

[0010] In Multiscalar Processor, a single program is divided into “tasks” as aggregate of basic blocks, and the “tasks” are processed by a processor which can executes those tasks in parallel. Transfer of register contents between “tasks” is designated by a task descriptor generated by a task compiler.

[0011] In the task descriptor, a register which may be generated is explicitly designated. This designation is referred to as create mask. On the other hand, for an instruction updating the register finally designated by the create mask, a forward bit is added. Thus, multiscalar processor performs parallel execution by a code depending upon decoding ability of the compiler.

[0012] One example of a construction of the multiscalar processor is shown in FIG. 24. In FIG. 24, the multiscalar processor is constructed with a sequencer 6, processing units 7-1 to 7-3, an associative network 8 and data banks 9-1 to 9-3.

[0013] Each of a plurality of the processing units 7-1 to 7-3 in the system is constructed with a cache 71, an execution unit 72 and a register file. On the other hand, corresponding to the processing units 7-1 to 7-3, a plurality of data banks 9-1 to 9-3 are provided. Each of the data banks 9-1 to 9-3 is constructed with an address resolution buffer (ARB) and data cache 91.

[0014] Management of simultaneous execution of a plurality of tasks is performed by the sequencer 6 which assigns task to the processing units 7-1 to 7-3. The content of each register of the register file is forwarded at a timing of data generation by designation of task descriptor.

[0015] On the other hand, in “Proposal for Directivity Control Parallel Architecture of On-chip Multiprocessor (MUSCAT)”, (Torii, Kondo, Motomura, Konagaya, Nishi, JSPP 97, pp 229 to 236, May 1997), there has been proposed a fork one time model limiting the fork for only one time during a thread life period is a period, in which one thread generates a thread by a fork instruction, and a thread execution model, performing lamp inheriting of all registers of the register file upon thread generation.

[0016] An image of the fork one time model is shown in FIG. 23. The fork one time model generates new thread for only one time during life period of the threads #1 to #3. By introduction of this model, simplification of thread management can be realized.

[0017] Furthermore, in a technology disclosed in Japanese Unexamined Patent Publication No. 10-078880, several kinds of methods for realizing register inheriting method by the fork one time model has been disclosed. Among these inheriting method, most of the method employs a method to finally copy the register content while timings are different. However, copying of the register content causes increasing of physical amount and hindering of speeding up.

[0018] Therefore, in the technology disclosed in the above-identified Japanese Unexamined Patent Publication No. 10-078880, there has been proposed an example, realizing inheriting of the register content by providing common registers with separating the register into logical registers and physical registers and only mapping image indicative of relationship between the logical register and the physical register is copied, as out-to-order issuing system, in which instructions are issues in non-order irrespective of the program order.

[0019] An example of the construction of the processor of this type is shown in FIG. 25. In FIG. 25, there is shown a construction of a two thread parallel execution type processor which is constructed with a common physical register file 126 common to thread execution units 121aand 121b, a register busy table 129, a register free table 130 and a thread management unit 131.

[0020] Each of the thread execution units 121aand 121bis constructed with instruction caches 122aand 122b, instruction decoders 123aand 123b, register mapping tables 124aand 124b, instruction queues 125aand 125b, arithmetic units 127aand 127band effective instruction order buffers 128aand 128b.

[0021] In the shown processor, the register is separated into a logical register to be accessed from the software and a physical register holding a register content in hardware, and a mapping relationship is held in the register mapping tables 124aand 124b.

[0022] Detailed construction of the register mapping tables 124aand 124bis shown in FIG. 26. In FIG. 26, the register mapping tables 124aand 124bhas a physical register number entry of registers 0 to 31 to convert into register numbers “45”, “13”, “04”, “21”, -, “53”.

[0023] Upon generation of the thread, by copying the mapping information between the register mapping tables 124aand 124b, register inheriting is realized without performing copy of the register content.

[0024] In the foregoing conventional multithread microprocessor, in case of the in-order issuing type in the register inheriting system of the register, in the above-mentioned publication, it becomes necessary to copy the content of the register upon initiation of the thread and termination of the thread.

[0025] On the other hand, in case of the out-of-order issuing type, copying of the register content becomes unnecessary. However, a common register free table between the thread execution units indicative of use/non-use of the register becomes necessary to cause a problem of complication of logic and data path and increasing of data amount. On the other hand, register renaming per one instruction is required to be too wasteful in application for the in-order issuing type.

[0026] Therefore, the present invention has been worked out for solving the problems set forth above. It is an object of the present invention to provide a register content inheriting system in a multi-processor which can achieve high efficiency both for in-order issuing type and out-of-order issuing type and high performance for fine threads. In order to accomplish the above-mentioned and other objects, according to one aspect of the present invention, a register content inheriting system in a multi-processor logically having a plurality of program counters and the multi-processor including a plurality of thread execution units simultaneously fetching, decoding and executing a plurality of threads according to the plurality of program counters, comprises:

[0027] a physical common register file common between respective of the plurality of thread execution units and consisted of a plurality of physical registers;

[0028] a conversion table provided for each of the plurality of thread execution units and defining a mapping relationship between one logical register in the thread execution unit and particular one of the plurality of physical registers in the physical common register file;

[0029] means for copying information of the conversion table of each of the plurality of thread execution units to an adjacent thread execution unit, group being established per a plurality of physical registers, in which the mapping relationship is defined between one logical register, and information indicative of position within each group being added to the information of the conversion table for defining the mapping relationship.

[0030] Namely, the register content inheriting system in the multi-processor according to the present invention is provided with a constraint in assignment relationship between the logical register and the physical common register file in order to accomplish the object set forth above.

[0031] This is the constraint that the physical common register file is divided into groups in number corresponding to number of the physical registers, and the physical register is assigned to the physical register belonging in one group of the physical common register file in mapped relationship.

[0032] The mapped relationship is a pointer information indicative where the physical register is arranged in the physical register file. Upon inheriting the content of the register, the pointer is copied to advance the mapping pointer only once upon updating of the register by the thread after inheriting for realizing independent operation after generation of inheriting of the register content upon thread generation.

[0033] By this, without performing copying of the content of the register, high performance can be achieved in high efficiency and fine thread either in in-order issuing type and out-of-order issuing type.

[0034] The present invention will be understood more fully from the detailed description given herebelow and from the accompanying drawings of the preferred embodiment of the present invention, which, however, should not be taken to be limitative to the invention, but are for explanation and understanding only.

[0035] In the drawings:

[0036] FIG. 1 is an illustration showing a basic concept of the first embodiment of a register content inheriting system in a multi-processor according to the present invention;

[0037] FIG. 2 is a block diagram showing one embodiment of the register content inheriting system in the multi-processor according to the present invention;

[0038] FIG. 3 is an illustration showing a pipeline stage in each thread execution unit of FIG. 2;

[0039] FIG. 4 is an illustration showing a construction showing a detail of a physical common register file of FIG. 2;

[0040] FIG. 5 is an illustration showing a format of a physical register of FIG. 4;

[0041] FIG. 6 is an illustration showing a detailed construction of a register mapping table of FIG. 2;

[0042] FIG. 7 is an illustration showing a detailed construction of one entry of the register mapping table of FIG. 2;

[0043] FIG. 8 is an illustration for explaining a mechanism showing transition of a group selection bit, physical expansion bit and modifying bits in normal operation and thus realizing the register content inheriting, in the first embodiment of the present invention;

[0044] FIG. 9 is an illustration for explaining a mechanism showing transition of a group selection bit, physical expansion bit and modifying bits in speculative thread generation and thus realizing the register content inheriting, in the first embodiment of the present invention;

[0045] FIG. 10 is an illustration showing a timing of copying a mapping information in the pipeline operation shown in FIG. 3;

[0046] FIG. 11 is an illustration showing a detailed construction of a register mapping table in the second embodiment of the present invention;

[0047] FIG. 12 is an illustration showing the detailed construction of one entry of the register mapping table of FIG. 11;

[0048] FIG. 13 is an illustration for explaining a mechanism showing transition of a group selection bit, physical expansion bit and modifying bits in normal operation and thus realizing the register content inheriting, in the second embodiment of the present invention;

[0049] FIG. 14 is an illustration for explaining a mechanism showing transition of a group selection bit, physical expansion bit and modifying bits in speculative thread generation and thus realizing the register content inheriting, in the second embodiment of the present invention;

[0050] FIG. 15 is a block diagram showing a construction of the third embodiment of the register content inheriting system in the multi-processor according to the present invention;

[0051] FIG. 16 is an illustration showing a detailed construction of the register mapping table of FIG. 15;

[0052] FIG. 17 is an illustration showing a detailed construction of the register effectiveness table of FIG. 15;

[0053] FIG. 18 is an illustration showing a pipeline stage in each thread executing unit of FIG. 15;

[0054] FIG. 19 is an illustration showing a timing of copying the mapping information in the operation of pipeline shown in FIG. 18;

[0055] FIG. 20 is an illustration showing an effective/null determination logic in the register effectiveness table shown in FIG. 17;

[0056] FIG. 21 is a block diagram showing the fourth embodiment of the register content inheriting system in the multi-processor according to the present invention;

[0057] FIG. 22 is an illustration showing a detailed construction of the register mapping table of FIG. 21;

[0058] FIG. 23 is an illustration showing a concept of the conventional form one time model;

[0059] FIG. 24 is a block diagram showing the construction of the conventional multiscalar multi-processor;

[0060] FIG. 25 is an illustration showing a construction of the multithread multi-processor using the conventional register mapping table; and

[0061] FIG. 26 is a block diagram showing a construction of the register mapping table of the multi-processor of FIG. 24.

[0062] The present invention will be discussed hereinafter in detail in terms of the preferred embodiment of the present invention with reference to the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be obvious, however, to those skilled in the art that the present invention may be practiced without these specific details. In other instance, well-known structures are not shown in detail in order to avoid unnecessarily obscure the present invention.

[0063] FIG. 1 is an illustration showing a basic concept of the first embodiment of a register content inheriting system in a multi-processor according to the present invention. In FIG. 1, for a logical register 10-0 to be used from a program on a thread executing unit (#0) 1-0 and for a logical register 10-1 to be used from a program on a thread executing unit (#1) 1-1, entries in a physical common register are assigned. Then, inheriting of the thread of the register is achieved without copying the real value of the registers by copying the assignment mapping information between the register mapping table (#0) 11-0 of the thread executing unit (#0) 1-0 and the register mapping table (#1) 11-1 of the thread executing unit (#1) 1-1.

[0064] FIG. 2 is a block diagram showing a construction of the first embodiment of the register content inheriting system in the multi-processor according the present invention. It should be noted that FIG. 2 shows a four thread parallel execution type multi-processor.

[0065] The multi-processor includes four sets of thread executing units (#0 to #3) 1-0 to 1-3, and a physical common register file 2.

[0066] Respective of the thread executing units 1-0 to 1-3 include instruction caches (#0 to #3) 12-0 to 12-3, instruction decoders (#0 to #0) 13-0 to 13-3, register mapping tables (#0 to #3) 11-0 to 11-3, and arithmetic units (#0 to #3) 14-0 to 14-3.

[0067] On the other hand, the register mapping tables 11-0 to 11-3 are connected with adjacent register mapping tables 11-0 to 11-3 for forming a ring form by a mapping information transfer bus 100. The multi-processor further requires a load store unit, data cache memory, external interface and so forth in addition to the foregoing construction. However, since such additional components are not directly relevant for the present invention, those components will be neglected from disclosure and illustration on the drawings.

[0068] FIG. 3 is an illustration showing a pipeline stage of each thread execution unit 1-0 to 1-3. In FIG. 3, in the pipeline state in each thread executing unit 1-0 to 1-3, execution of instruction is completed through 5 stages consisted of an instruction fetching stage 31, an instruction decoding stage 32, a register converting stage 33, an arithmetic stage 34, a register writing back stage 35.

[0069] FIG. 4 is an illustration showing a detailed construction of the physical common register file 2 of FIG. 2. The physical register file 2 is constructed with physical registers 21 in number of double of the number of the thread executing units 11-0 to 11-3 per each logical register number 22. Accordingly, in the shown embodiment, for one logical register, eight logical registers 21 are corresponded.

[0070] Each physical register 21 is divided into two groups 24 and 25 of A and B of group selection bits 23 and had physical expansion bits 26 in number corresponding to the number of the thread execution units 11-0 to 11-3.

[0071] FIG. 5 is an illustration showing a format of the physical register 21 of FIG. 4. In FIG. 5, when the physical register 21 is an instruction set having thirty-two logical register set, it is constituted of the physical expansion bits 26, the group selection bits 23 and the logical register number 22. In this case, when the number of the logical register sets is varied, the bit number indicative of the logical register number 22 is varied, and when the number of the thread executing unit 1-0 to 1-3 is varied, the value of the physical expansion bit 26 is varied.

[0072] FIG. 6 is an illustration showing a detailed construction of the register mapping table 11 of FIG. 2. In FIG. 6, the register mapping table 11 is divided into groups A and B selected by the group selection bit 41 per logical register number 22. The register mapping table 11 is consisted of a physical expansion bit 43, a modification bit 44, a write back bit 45 and a on-inherit group selection bit 22.

[0073] The group selection bit 41 represents a group of the common physical register file 2 which is made reference to by the thread execution units 1-0 to 1-3, and which of the physical register 21 therein is to be made reference to, is indicated by the physical expansion bit 43.

[0074] The modification bit 44 represents whether the instruction for updating the physical register 21 selected by the group selection bit 41 is decoded for one or more times by the thread execution unit 1-0 to 1-3, or not.

[0075] The write back bit 45 represents whether one ore more instruction updating the physical register 21 has been actually completed or not. The on-inheriting group selection bit 42 is one for which the content of the group selection bit 41 is copied at a timing where the register content is inheritred from one thread execution unit 1-0 to 1-3 from the other thread execution unit 1-0 to 1-3.

[0076] FIG. 7 is an illustration showing a detailed construction of one entry of the register mapping table 11 of FIG. 2. In FIG. 7, the register mapping table 11 is provided with adders 51aand 51b, multiplexers 52ato 52d, and a write operation logic 53 in addition to the bits shown in FIG. 6.

[0077] The group selection bit 41 is set when a fork in fork one time model is modified, namely when the register value is modified for the first time by the instruction of the thread execution unit 1-0 to 1-3 after performing thread generation.

[0078] Judgment whether re-writing is the first time after fork or not is performed based on an exclusive OR of the values of the group selection bit 41 and the on-inherit group selection bit 42. The on-inheriting group selection bit 42 can perform judgment for holding the copy of the group selection bit 41 upon thread generation.

[0079] On the other hand, the modification bits 44aand 44bare reset the group side selected by the group selection bit 41 upon initiation of own thread and set the non-selected side group. Subsequently, when the instruction for modifying the register value is received from the instruction decoder 13, modification bits 44aand 44bon the side selected by the group selection bit 41 are set.

[0080] The write back bits 45aand 45bis reset on the side selected by the group selection bit 41 and set on the on-selected side, upon initiation of own thread. The write back bits 45aand 45bwhich is in reset is set when the result actually calculated by the arithmetic unit 14 is written back to the physical common register file 2.

[0081] By this, expansion of the physical register number is performed for the physical register 10 according to a principle of making reference set forth below. At first, upon reading reference, the multiplexers 52aand 52bdirectly outputs the values of the physical expansion bits 43aand 43bwhen the modification bits 44aand 44bare reset, and outputs values derived by adding one to the values of the physical expansion bits 43aand 43bby the adders 51aand 51b, when the modification bits 44aand 44bare set.

[0082] By adding one to the values of the physical expansion bits 43aand 43b, conflict of register in the physical common register file 2 to be used on the non-selected side is avoided. Since the non-selected side is used upon modification in own unit, prevention of occurrence of conflict of the registers can be realized by preventing use of the same register in the unit of the preceding stage and the own unit or in the unit of the following stage and the own unit.

[0083] The multiplexer 52cselects out one of the values of the A group and B group to read out to output as the physical expansion bit 26 for reference depending upon the group selection bit 41.

[0084] On the other hand, the physical expansion bit 26 for writing reference is required to constantly output the value derived by adding one to the values of the physical expansion bits 43aand 43birrespective of selection of the group between the A group and B group.

[0085] Accordingly, as input for the multiplexer 52d, a value derived through the adders 51aand 51bfrom the physical expansion bits 43a and 43b in either of A group and B group. Selection of the A group or B group is basically performed according to the value of the group selection bit 41. However, upon switching the group selection bit 41 set forth above, precedingly switched one is selected.

[0086] The control is performed by writing operation unit 53. On the other hand, the physical expansion bits 43aand 43bare returned to zero when preliminarily provided digits is overflowed by addition. Furthermore, upon generation of thread, the group selection bit 41 and the physical expansion bits 43aand 43boutput from the multiplexers 52aand 52bare copied via the register mapping table 11 of thread generating destination.

[0087] Hereinafter, register reference operation after initiation of thread, operation upon thread generation and register reference operation after thread generation will be discussed in order to timing. The following discussion will be given for operation to be performed by the register conversion stage 33 in FIG. 3.

[0088] FIG. 8 is an illustration for explaining a mechanism of transition of values of the group selection bit 41, the physical expansion bits 43aand 43band the modification bits 44aand 44bduring normal operation in the first embodiment of the present invention, and a mechanism of realizing register content inheriting by transition of the values. It should be noted that operation of the write back bits 45aand 45bis neglected herein and will be discussed later.

[0089] At a timing (a) of initiation of a new thread by the thread execution unit (#0) 1-0, the group selection bit 41 is set “A”. On the selected side “A”, the physical expansion bit 43ais set to zero and the modification bot 44ais also set to zero.

[0090] On the non-selected side, the physical expansion bit 43bis set zero whereas the modification bit 44bis preliminarily set “1” for non-selected side. In this case, the logic register 10 makes reference to by reading the physical register 21 positioned at zero of “A”.

[0091] At the occurrence of write reference, namely at a timing (b) of register variation, the modification bit 44a of “A” is set to one. Variation is performed for the physical register 21 positioned at one of “A”, subsequent reading reference is performed for the same register. Thereafter, writing reference for the same register is caused, the group selection bit 41 and the modification bits 44a and 44b are not modified.

[0092] Next, at a timing (C) for generating new thread, since the group selection bit 41 is “A”, “A” is set in either of “A” and “B” of the modification bits 44aand 44b. Therefore, the values derived by adding one to the physical expansion bits 43aand 43bare transmitted to the register mapping table 11-1 of the thread execution unit (#1) 1-1.

[0093] Upon performing register write reference for the first time after thread generation by the thread execution unit (#0) 1-0, namely, the group selection bit 41 is varied from “A” to “B” at a timing (d). Variation is performed for the physical register 21 positioned at ol of “B”. Subsequently, reading reference is also performed for the same register.

[0094] Even if writing reference is caused for the same register, the group selection bit 41 or modification bits 44aand 44bare not varied. By this, the register value which can make reference to by the thread execution unit (#1) 1-1 is held at the position of 0 of “A”.

[0095] In the thread execution unit (#1) 1-1, new thread is generated at a timing (e) without causing write reference of the register. Accordingly, the physical expansion bit 43a of “A” on the group of the selected side is transmitted the value as it is. Accordingly, the register content of the thread executed by the thread execution unit (#0) 1-0 is transferred to the thread executed by the thread execution unit (#2) 1-2. On the other hand, when the register modification is performed at the timing (f), since the timing is after fork, the group selection bit 41 is switched from “A” to “B”.

[0096] FIG. 9 is an illustration for explaining mechanism for transition of values of the group selection bit 41, physical expansion bit 43aand 43band modification bit 44aand 44band whereby for realizing register content inheriting. Among operation shown in FIG. 9, (a) to (d) are the same as operations of (a) to (d) of FIG. 8.

[0097] At a timing of (e), the thread execution unit (#0) 1-0 cancels the thread generated at the timing (c). Also, at a timing (f), the thread is generated again. Since the group selection bit 41 is “B”, “B” is set. The modification bits 44aand 44bare set “A” and “B”. Therefore, the values derived by adding one to the values of the physical expansion bits 43aand 43bare transmitted to the register mapping table 11 of the thread execution unit (#1) 1-1.

[0098] By this, the value varied at the timing (d) is inherited to the thread to be executed by the thread execution unit (#1) 1-1. At a timing (g), when the content of the register is varied, the group selection bit 41 is returned to “A”, again.

[0099] FIG. 10 is an illustration showing a timing of copying the mapping information in the pipeline operation shown in FIG. 3. In FIG. 10, copying of the register mapping information is performed in such a manner that the thread generation instruction is transmitted in the register conversion stage (cycle 5 of FIG. 19). In the register conversion stage, the register inheriting information is transmitted from the thread execution unit (#0) 1-0. Then, in the next cycle (cycle 6 of FIG. 10), the register inheriting information is written in the register mapping table 11 of the thread execution unit (#1) 1-1. It should be noted that the content of the group selection bit 41 of the register mapping table 11 of the thread execution unit (#0) 1-0 is copied together with the on-inheriting group selection bit 42 in the same register mapping table 11.

[0100] In the normal instruction E at cycle 7, the register inherited with reference to the register mapping table 11 is accesses. At a timing where the thread execution units 1-0 to 1-3 in the thread generating destination is in execution of other thread and where the thread generation demand becomes acceptable following the condition where new thread generation demand is not accepted, the value of the on-inheriting group selection bit 42 may be transmitted in place of the group selection bit 41.

[0101] Finally, discussion will be given with respect to write back bits 45aand 45b. The write back bits 45aand 45bare used for returning the modification bits 44a and 44b to correct values when instruction requiring write reference to the register is canceled in certain cause (for example, failure of prediction of the condition branch instruction or so forth).

[0102] One of the write back bits 45aand 45bon the selected side is reset and the other on the non-selected side is set by the group selection bit 41. The write back bits 45aand 45bwhich is in reset condition, is set when the result of actual calculation by the arithmetic unit 14 is written back in the physical common register file 2.

[0103] Namely, the fact that the modification bits 44aand 44bare set and the write back bits 45aand 45bare not set, represent that the instruction for setting the modification bits 44aand 44bare not yet completed.

[0104] Accordingly, when cancellation of the instruction occurs at this stage, the content of the write back bits 45aand 45bare copied to the modification bits 44aand 44bto return to the initial values to return the register mapping table 11 to normal value upon cancellation of instruction.

[0105] By the foregoing method, inheriting of the register is realized without copying the actual content of the register and with taking only physical common register file 2 as common resource.

[0106] Each physical expansion bit 26 is added merely one upon-inheriting. Therefore, by providing two sets of register groups of the number corresponding to the thread execution units 1-0 to 1-3, the foregoing mechanism can be realized.

[0107] FIG. 11 is an illustration showing the detailed construction of the register mapping table in the second embodiment of the present invention. In FIG. 11, the second embodiment of the present invention is similar to the first embodiment of the present invention illustrated in FIGS. 1 to 5 except for a construction of the register mapping table 11.

[0108] In FIG. 11, the register mapping table 11 is divided into groups A and B to be selected by the group selection bit 41 per logical register number 22. Each of the A group and B group is consisted of the physical expansion bit 43, the modification bit 44, the write back bit 45. Also, the register mapping table 11 has the on-inheriting group selection bit 42 and a group selection modification instruction incompletion bit 46.

[0109] The group selection bit 41 represents the group of the physical common register file 2 to which the thread execution unit 1 makes reference to. Together with the physical expansion bit 43, the physical register 21 to be assigned is determined depending upon the logical registration number 22.

[0110] The modification bit 44 represents whether the instruction for updating the physical register 21 selected by the group selection bit 41 is decoded for one or more times by the thread execution units 1-0 to 1-3.

[0111] The write back bit 45 represents whether the instruction for updating the physical register 21 is actually completed for one or more times, or not. The on-inheriting group selection bit 42 is the copy of the content of the group selection bit 41 at a timing where the register content is inherited from one thread execution units 1-0 to 103 to the other thread execution units 1-0 to 1-3.

[0112] FIG. 12 is an illustration showing a detailed construction of the entry of the register mapping table 11 of FIG. 11. In FIG. 12, the register mapping table 11 is provided with adder 51aand 51b, the multiplexers 52ato 52fand write operation logic 53, in addition to the bits shown in FIG. 11.

[0113] The group selection bit 41 is reset (representing the side “A”) when the value before modification is set (representing the side “B”) and is set (representing the side “B”) when the value before modification is reset (representing the side “A”) when the instruction for modifying the register value by writing at the first time in response to the instruction of the thread execution unit 1-0 to 1-3 after fork in the fork one time model, namely after performing thread generation.

[0114] When the group selection bit 41 and the on-inheriting group selection bit 42 are the same, re-writing at the first time after fork is detected. Since the on-inheriting group selection bit 42 stores the copy of the group selection bit 41 upon thread generation, this judgment can be performed.

[0115] The group selection modification instruction incompletion bit 46 is set when the instruction for varying the group selection bit 41 passes the register conversion stage 33, and is reset at a timing where the instruction reaches the write back stage 35.

[0116] The modification bits 44aand 44bare reset the group side selected by the group selection bit 41 upon initiation of own thread. Subsequently, when the instruction for modifying the register value is received from the instruction decoder 13, modification bits 44aand 44bon the side selected by the group selection bit 41 is set.

[0117] The write back bits 45aand 45bis reset upon initiation of own thread. The write back bits 45aand 45bwhich is in reset is set when the result actually calculated by the arithmetic unit 14 is written back to the physical common register file 2.

[0118] By this, expansion of the physical register number is performed for the physical register 10 according to a principle set forth below. At first, upon reading reference, the multiplexers 52aand 52bdirectly outputs the values of the physical expansion bits 43aand 43bwhen the modification bits 44aand 44bare reset, and selects values derived by adding one to the values of the physical expansion bits 43aand 43bby the adders 51aand 51b, when the modification bits 44aand 44bare set.

[0119] Among these values, the value of A group or B group is selected by a value indicated by the group selection bit 41 in the multiplexer 52cto output as the physical expansion bit 26 for reading reference.

[0120] Even if the either A group or B group is selected as the physical expansion bit upon modification of the writing register, the values derived by adding one to the values of the physical expansion bits 43aand 43bby the adders 51aand 51bare output. Therefore, as the input for the multiplexer 52d, the values past through the adders 51aand 51bfrom the physical expansion bits 43aand 43bare used in either case of A group and B group.

[0121] Selection of A group and B group is performed according to the value of the group selection bit 41. In case of register variation associating with re-writing of the group selection bit 41, the group after re-writing is selected.

[0122] Control is performed by writing operation logic 53. On the other hand, when the preliminarily provided digit is overflowed by addition to the values of the physical expansion bits 43aand 43b, the value is returned to zero. Furthermore, upon thread generation, the value has to be set to the value in the mapping table in the thread generation destination.

[0123] This value is determined on the basis of the value of the mapping table 11 of the thread generation source.

[0124] At first, the group selection bit 41 is set to the same value as the group selection bit 41 of the mapping table 11 of the thread generation source. Next, the values of the physical expansion bits 43aand 43bbecome values derived by adding one to the values of the physical expansion bits 43aand 43bwhen the modification bits 44aand 44bcorresponding to the physical expansion bits 43aand 43bof the group selected by the group selection bit 41 of the mapping table 11 of the thread generation source are set, and become values of the physical expansion bits 43aand 43bwhen the modification bits 44aand 44bare not set.

[0125] On the other hand, in the physical expansion bits 43aand 43bof the group not selected by the group selection bit 41 of the mapping table 11 of the thread generation source, the values derived by adding one to the values of the physical expansion bits 43aand 43bare set. Then, the modification bits 44aand 44b, the write back bits 45aand 45b, the group selection modification instruction incompletion bit 46, on-inheriting group selection bit 42 are reset. At the same time, the mapping table of the thread generation source, the value of the group selection bit 41 is copied to the on-inheriting group selection bit 42.

[0126] Thus, after modification of register by writing, by using the values derived by adding one to the values of the physical expansion bits 43aand 43b, the logical register number to be used in the thread execution units 1-0 to 1-3 become equal to those in the same physical bits 26 in the physical common register file upon-inheriting of register content. On the other hand, when modification is effected, the logical register number becomes equal to the different physical bit 26. Thus, by the thread execution units 1-0 to 1-3, logically independent logical registers 10-0 and 10-1 and register content inheriting can be realized.

[0127] Hereinafter, register reference operation after initiation of thread, operation upon thread generation and register reference operation after thread generation will be discussed in order to timing. The following discussion will be given for operation to be performed by the register conversion stage 33 in FIG. 3.

[0128] FIG. 13 is an illustration for explaining a mechanism of transition of values of the group selection bit 41, the physical expansion bits 43aand 43band the modification bits 44aand 44bduring normal operation in the second embodiment of the present invention, and a mechanism of realizing register content inheriting by transition of the values. It should be noted that operation of the write back bits 45aand 45bis neglected herein and effects of the write back bits 45aand 45band the group selection modification instruction incomletion bit 46 will be discussed later.

[0129] At a timing (a) of initiation of a new thread by the thread execution unit (#0) 1-0, the group selection bit 41 is set “A”. On the selected side “A”, the physical expansion bit 43ais set to zero and the modification bit 44ais also set to zero. On the non-selected side “B”, the physical expansion bit 43bis set zero whereas the modification bit 44bis set zero.

[0130] In this case, upon reading out the content of the register, reference is made to the physical register 21 located at the position of 0 of “A”. When the register conversion stage 33 is reached by issuing instruction performing modification by register writing, namely at the timing of register modification (b), modification bit 44aof “A” is set to one.

[0131] Modification is performed for the physical register 21 located at the position 1 of “A”, and subsequently, reading reference is performed for the same register. Thereafter, even when writing reference is caused for the same register, the group selection bit 41 and the modification bit 43aare held unchanged.

[0132] Next, at a timing (c) where new thread is generated, the value of the group selection bit 41 (here “A”), the value derived by adding one to the value of the physical expansion bit 43a(here 1) since the modification bit 44ais set as selected side “A” and value derived by adding one to the value of the physical expansion bit 43birrespective of the modification bit 44b(here 1) on the non-selected side are transmitted to the register mapping table 11 of thread execution unit (#1) 1-1.

[0133] When the thread execution unit (#0) 1-0 issues the instruction for performing register writing reference at the first time after generation of the thread, namely at a timing (d), the value of the group selection bit 41 is switched from “A” to “B” and the modification bit 44bis set.

[0134] Modification is performed for the physical register 21 loaded at the position of 1 of “B”. Subsequently, the reading reference is performed for the same register.

[0135] Thereafter, even when writing reference for the same register is caused, the group selection bit 41 and the modification bit 44bare held unchanged. By this, the register value which can be made reference to by the thread execution unit (#1) 1-1 is held at the position of 0 of “A”.

[0136] In the thread execution unit (#1) 1-1, without inducing the writing reference of the register, new thread is generated at a timing (e). Accordingly, the physical expansion bit 43aof “A” of the group on the selected side transmits its own value. Therefore, the content of the register of the thread executed by the thread execution unit (#0) 1-0 is transferred by the thread executed by the thread execution unit (#2) 1-2. On the other hand, upon performing register modification at a timing (f), since the timing is after fork, the value of the group selection bit 41 is switched from “A” to “B” and then, the modification bit 44bis set.

[0137] FIG. 14 is an illustration showing a mechanism of transition of values of the group selection bit 41, the physical expansion bits 43aand 43band modification bits 44aand 44bin the case where speculative thread generation is performed in the second embodiment of the present invention, and whereby realizing inheriting of the content of the register. Among operations shown in FIG. 14, (a) to (d) are the same as operations of (a) to (d) of FIG. 13.

[0138] At a timing of (e), the thread execution unit (#0) 1-0 cancels the thread generated at the timing (c). Also, at a timing (f), the thread is generated again. Since the group selection bit 41 is “B”, “B” is transmitted to the register mapping table 11 of the thread execution unit (#1) 1-1. Likewise, since the modification bit 44bis set on the selected side “B”, the value derived by adding one to the valve of the physical expansion bit 43bis transmitted to the register mapping table 11 of the thread execution unit (#1) 1-1. Also, on the non-selected side A, the value derived by adding one to the value of the physical expansion bit 43ais transmitted to the register mapping table 11 of the thread execution unit (#1) 1-1 irrespective of the value of the modification bit 44a. The modification bits 44aand 44bare set “A” and “B”.

[0139] By this, the value varied at the timing (d) is transferred to the thread to be executed by the thread execution unit (#1) 1-1. At a timing (g), when the content of the register is varied, the group selection bit 41 is returned to “A”, again.

[0140] Finally, effects of the write back bits 45aand 45band group selection modification instruction incompletion bit 46 will be discussed. When the instruction for making reference to in writing in the register is canceled in certain reason (for example, failure of prediction of the condition branching instruction), the group selection modification instruction incompletion bit 46 is used for returning the group selection bit 41 to the condition before execution of the writing reference instruction which is canceled.

[0141] The write back bits 45aand 45bare reset upon initiation of own thread. The write back bits 45aand 45bare set when the result of actual calculation calculated by the arithmetic unit 14 is written back in the physical common register file 2, namely, at the register write back stage 35 in FIG. 3.

[0142] On the other hand, upon issuing the register writing instruction, namely at register conversion stage 33, the modification bits 44aand 44bare set. From these, the condition where the modification bits 44aand 44bare set and the write back bits 45aand 45bare not set, represents a condition where the instruction for setting the modification bits 44aand 44bare not completed.

[0143] Accordingly, when cancellation of the instruction at this stage is caused, by copying the content of the write back bits 45aand 45bto the modification bits 44aand 44b, it becomes possible to return the value to that before execution of writing reference of the cancelled instruction.

[0144] The group selection modification instruction incompletion bit 46 is reset upon initiation of thread. When the instruction for modifying the group selection bit 41 reaches the register conversion stage 33, the group selection modification instruction incompletion bit 46 is set. The group selection modification instruction incompletion bit 46 is reset when the instruction reaches the register write back stage 35. Namely, while the group selection modification instruction incompletion bit 46 is set, it indicates that the instruction for modifying the group selection bit 41 is not completed.

[0145] When cancellation of the instruction is caused in this condition, the group selection bit 41 corresponding to the set group selection modification instruction incompletion bit 46 is reversed. Subsequently, the group selection modification instruction incompletion bit 46 is reset. By these process, upon cancellation of instruction, the register mapping table 11 can be returned to the condition before execution of the instruction.

[0146] By the method discussed above, it becomes possible to realize inheriting of the content of the register with taking only physical common register file 2 as the common resource without performing copying of the actual content of the register.

[0147] Each physical expansion register 26 is merely added one upon-inheriting. Therefore,the foregoing mechanism can be realized by providing two sets of register groups in number corresponding to the number of the thread execution units 1-0 to 1-3.

[0148] Next, the third embodiment of the present invention will be discussed. The third embodiment of the present invention is similar to the first embodiment of the present invention. The following discussion will be given for difference of the shown embodiment relative to the first embodiment.

[0149] FIG. 15 is a block diagram showing a construction of the third embodiment of the register content inheriting system in the multi-processor. In FIG. 15, there is illustrated a construction of a four thread parallel execution type multi-processor.

[0150] The multi-processor in the third embodiment of the present invention has similar construction as the multi-processor in the first embodiment of the present invention except for the register mapping tables (#1 to #3) 63-0 to 63-3 provided in place of the register mapping tables (#0 to #3) 11-0 to 11-3 of the foregoing first embodiment. It should be noted that, in the following disclosure, like elements to those in the first embodiment will be identified by the same reference numerals and detailed description thereof will be neglected for avoiding redundant discussion and whereby for keeping the disclosure simple enough to facilitate clear understanding of the present invention.

[0151] The third embodiment of the multi-processor according to the present invention is constructed with the thread management unit 3, the four sets of thread execution units (#0 to #3) 1-0 to 1-3, and a physical common register file 2.

[0152] Respective thread execution units 1-0 to 1-3 are constructed with instruction cache (#0 to #3) 12-0 to 12-3, instruction decoders (#0 to #3) 13-0 to 13-3, register mapping tables (#0 to #3) 63-0 to 63-3, instruction issuing queues (#0 to #3) 61-0 to 61-3, register effectiveness table 62-0 to 62-3, and arithmetic units (#0 to #3) 14-0 to 14-3.

[0153] On the other hand, the register mapping tables 63-1 to 63-3 are connected with adjacent register mapping tables through mapping information transfer bus 100 into a ring form.

[0154] The multi-processor is further provided a load/store unit, data cache memory, an external interface and so fort, in addition to the construction set forth above. However, such extra components are less relevant to the subject matter of the present invention. Therefore, these components are not illustrated and discussed.

[0155] FIG. 16 is an illustration showing the detailed construction of the register mapping table 63 of FIG. 15. In FIG. 15, the register mapping table 63 has similar construction as the register mapping table 11 shown in FIG. 6, except for a completive writing bit 64.

[0156] FIG. 17 is an illustration showing the detailed constructing of the register 62 of FIG. 15. In FIG. 17, the register effective has an effective bit 66 indicating effective/null of the values of the registers per each logical register number r0 to r31.

[0157] The register effectiveness table 62 is designed for indication that the value of the register inherited from the thread executed by other thread execution units 1-0 to 1-3 is fixed and thus effective or not fixed and thus null.

[0158] FIG. 18 is an illustration showing respective pipeline stage of the thread execution units 1-0 to 1-3 of FIG. 15. In the pipeline stage in each thread execution unit 1-0 to 1-3, execution of the instruction is completed through the instruction fetching stage 31, the instruction decoding stage 32, the register conversion table 33, the instruction issuing queue 61, the instruction issuing stage 65, the execution stage 34, the register write back stage 35. It should be noted that the instruction issuing stage 65 and subsequent stage can be realized by execution in out-of-order.

[0159] The instruction issuing queue performs 61 is into waiting until the value of the register which is to be used, reaches the value where the register value becomes effective.

[0160] FIG. 19 is an illustration showing a timing of copying the mapping information on in the operation of the pipeline. In FIG. 19, by employing the instruction issuing queue 61, it becomes possible to perform write back in out-of-order without performing write back in the program order shown in FIG. 10.

[0161] Accordingly, on the side of the thread execution units 1-0 to 1-3, in which execution of new thread is initiated, the register value which is inherited cannot be made reference to unless writing back is completed in the thread execution units 1-0 to 1-3 as initiated. In order to permit checking of completion of the write back operation, the register effectiveness table 62 is used.

[0162] When reading reference is made in the register mapping table 63, if the modification bits 44aand 44bof the group selected by the group selection bit 41 are set, the effective bit 66 has to be checked upon issuance of the instruction.

[0163] If the modification bits 44aand 44bare not set, checking of the effective bit 66 is not necessary.

[0164] FIG. 20 is an illustration showing a logic for determining effective/null in the effectiveness table 62 shown in FIG. 17. Setting and resetting method of the register effectiveness table 66 will be discussed with reference to FIGS. 17 to 20.

[0165] Respective effective bits 66 of the register effectiveness tables 62-0 to 62-3 are connected to respectively adjacent register mapping tables 63-0 to 63-3 of the thread execution units 1-0 to 1-3. The register effectiveness tables 62-0 to 62-3 receive effective/null information of the register from the register mapping tables 63-0 to 63-3 on a thread generation demanding side and feed the same information to the register effectiveness tables 63-0 to 63-3 adjacent on the opposite side.

[0166] The effective information is determined by the logic shown in FIG. 20 on the basis of combination of respective bits of the register mapping tables 62-0 to 62-3 and input signals from the register effectiveness tables 62-0 to 62-3 of the adjacent thread execution units 1-0 to 1-3.

[0167] Namely, in FIG. 20, in the thread execution unit #n, effective/null of the effective input to the thread execution unit #(n+1) in the following stage is determined depending upon the effective input from the thread execution unit # (n−1) in the preceding stage. On the other hand, when no effective input from the thread execution unit #(n−1) of the preceding stage is present, the effective/null of the effective unit to the thread execution unit #(n+1) of the following stage is determined depending upon completive write bit 64 in the thread execution unit #n.

[0168] The completive write bit 64 is set simultaneously with the modification bit 44. Upon writing back for the instruction for modifying the content of the register, whether writing instruction for the same register by general instruction up to the thread generation instruction is present or not is checked by comparing the instruction of the instruction issuing queue 61-0 to 61-3 and the instruction present in the execution stage 34 of the pipeline. If the instruction for modifying the content of the register is not present, the completive write bit 64 is reset.

[0169] Namely, the condition where the modification bit 44 is set and the completive write bit 64 is reset, represents that while the content of the register is rewritten up to thread generation, the value is reflected to the physical common register file 2. From this information, the register effectiveness tables 62-0 to 62-3 of the adjacent thread execution units 1-0 to 1-3 are set. When the modification bit 44 is not set, the information from the thread before that is set as is.

[0170] Subsequently, discussion will be given for the fourth embodiment of the present invention. The fourth embodiment of the present invention is similar to the second embodiment of the present invention. Different points of the fourth embodiment relative to the second embodiment will be discussed hereinafter. The fourth embodiment is realized by using respective components shown in FIGS. 17 to 20.

[0171] FIG. 21 is a block diagram showing the construction of the fourth embodiment of the register content inheriting system in the multi-processor according to the present invention. In FIG. 21, there is shown a construction of a four thread parallel execution type multi-processor.

[0172] The fourth embodiment of the multi-processor according to the present invention is similar to the second embodiment of the multi-processor according to the present invention except that register mapping tables (#0 to #3) 63-0 to 63-3 modified from the construction of the register mapping tables (#0 to #3) 11-0 to 11-3 of the second embodiment are provided and the instruction issuing queues 61-0 to 61-3, the register effectiveness tables 62-0 to 62-3 and effectiveness determining logic 67-0 to 67-3 are added. It should be noted that like components to those in the second embodiment set forth above will be identified by like reference numerals and detailed description therefor will be neglected in order to avoid redundant disclosure for keeping the disclosure simple enough to facilitate clear understanding of the present invention.

[0173] Namely, the fourth embodiment of the multi-processor according to he present invention is constructed with the thread management unit 3, four sets of thread execution units (#0 to #3) 1-0 to 1-3 and the physical common register 2.

[0174] Respective thread execution units (#0 to #3) 1-0 to 1-3 are constructed with instruction caches (#0 to #3) 12-0 to 12-3, instruction decoder (#O to #3) 13-0 to 13-3, the register mapping tables (#0 to #3) 63-0 to 63-3, the instruction issuing queues (#0 to #3) 61-0 to 61-3, the register effectiveness tables (#0 to #3) 62-0 to 62-3, the effectiveness determining logic (#0 to #3) 67-0 to 67-3 and arithmetic units (#0 to #3) 14-0 to 14-3.

[0175] On the other hand, the register mapping tables (#0 to #3) 63-0 to 63-3 are connected with adjacent register mapping tables (#1 to #3, #0) 63-1 to 63-3, 63-0 by the mapping information transfer bus 100 into a ring shape. The multi-processor further requires the load/store unit, data cache memory, the external interface and so forth in addition to the foregoing construction. Such additionally required components are not directly relevant for the present invention and thus are neglected from illustration and description.

[0176] FIG. 22 is an illustration showing the detailed construction of the register mapping table 63 of FIG. 21. The register mapping table 63 is similar to the register mapping table shown in FIG. 11 except for the completive write bit 64 as additional component. It should be noted that like components to those in FIG. 11 will be identified by like reference numerals and detailed description therefor will be neglected in order to avoid redundant disclosure for keeping the disclosure simple enough to facilitate clear understanding of the present invention.

[0177] In the fourth embodiment of the present invention, the register effectiveness table 62 indicates effective/null of the register value of other thread execution unit. Namely, in the shown case, the register effectiveness table (#0) 62-0 indicates whether the value of the register transferred from the thread executed by the thread execution units (#1 to #3) 1-1 to 1-3 is fixed and thus effective or not yet fixed and thus null (instruction for writing in the relevant register is not yet completed).

[0178] On the other hand, in the pipeline stage of the fourth embodiment of the present invention, respective pipeline stage of the thread execution units (#0 to #3) 1-0 to 1-3 is completed through six stages of the instruction fetching stage 31, the instruction decoding stage 32, the register conversion stage 33, the instruction issuing stage 65, the execution stage 34, the register write back stage 35. It should be noted that the instruction issuing queue 61 is inserted between the register conversion stage 33 and the instruction issuing stage 65, the instructions are executed from one ready to issue the instruction following the instruction issuing stage 65, in out-of-order.

[0179] The instruction issuing queue 61 performs issuance of instruction in out-of-order from the instruction becoming ready for issue. Therefore, the value of the register to be used by the instruction becoming effective is waited to keep the stand-by state for issuing the instructions from those becoming effective.

[0180] In the fourth embodiment of the present invention, by using the instruction issuing queue 61, writing back of the register in-order of the program shown in FIG. 10 is not performed and writing back in out-of-order is performed.

[0181] Accordingly, on the side of the thread execution unit (#1) 1-1 in which execution of the new thread is initiated, reading reference has to be restricted as long as the writing back on the side of the thread execution unit (#0) 1-0 in initiation side. In order to performing checking of completion of write back, the register effectiveness table 62 is employed.

[0182] The instruction for performing reading reference of certain register determines whether check has to be effected with the register effectiveness table 62 upon issuance of instruction in the register mapping table 63 at the register conversion stage 33, or not.

[0183] If the modification bit 44 of the group selected by the group selecting bit 41 of the register mapping table 63is not set, it becomes necessary to check the effective bit 66 upon issuance of instruction. When the modification bit 44 is set, it is unnecessary to check the effective bit 66. The reason is that since writing to the relevant register has already been done in the own thread, judgment can be made that inheriting of register content has been completed between the threads.

[0184] In the instruction issuing queue 61, upon checking whether the instruction can be issued or not for the instruction which is judged as checking of the effective bit 66 being necessary, the effective bit 66 of the register effectiveness table 62 is checked. As a result of checking, if null is indicated, such instruction is controlled so as not to be executed until it becomes effective.

[0185] In the fourth embodiment of the present invention, the effectiveness determining logic (#0) determines and outputs effective/null of the input with respect to the register effectiveness table (#1) 62-1 on the basis of the values of the register effectiveness table (″0) 62-0 and the register mapping table 63. Hereinafter, method of setting/resetting of the register effectiveness table 62 will be discussed with reference to FIGS. 21, 22 and 17 to 20.

[0186] The completive write bit 64 is set simultaneously with the modification bit 44. Upon writing back of the instruction for modifying register, whether the write instruction for the same register by the general instruction up to thread generating instruction is present or not, is judged by comparison of the instruction issuing queue and the instruction present in the execution stage of the pipeline.

[0187] If the write instruction is not present, the completive write bit 64 is reset.

[0188] Namely, the condition where the modification bit 44 is set and the completive write bit 64 is reset, represents that while the content of the register is rewritten up to thread generation, the value is reflected to the physical common register file 2.

[0189] When both of the modification bit 44 and the completive write bit 64 are set, the instruction for rewriting the register is issued until generation of the thread, it represents that the instruction is not completed.

[0190] In case of rewriting after fork, rewriting after fork from the on-inherit group selection bit 42 is performed by making judgment of the effectiveness determining logic 67 according to the logic of FIG. 20 to prevent outputting of the erroneous null signal.

[0191] The register effectiveness table 62 on the side where the thread is generated, sets the effective bit 66 by the value generated by the effectiveness determining logic 67 on the thread generation side to determine whether instruction can be issued from the instruction issuing queue 61 or not in a manner set forth above.

[0192] As set forth above, inheriting of the register content between the threads effectively using the fork one time model becomes possible without requiring data transfer through the common memory and thus permits effective execution of multithread.

[0193] On the other hand, inheriting of the content of the register can be realized between before and after the fork instruction without using the common resource other than the register. Therefore, it becomes possible to reduce overhead associating with thread generation, to use sole thread execution units 1-0 to 1-3 in high level, and to realize high speed multithread multi-processor.

[0194] Although the present invention has been illustrated and described with respect to exemplary embodiment thereof, it should be understood by those skilled in the art that the foregoing and various other changes, omissions and additions may be made therein and thereto, without departing from the spirit and scope of the present invention. Therefore, the present invention should not be understood as limited to the specific embodiment set out above but to include all possible embodiments which can be embodied within a scope encompassed and equivalents thereof with respect to the feature set out in the appended claims.

[0195] Namely, while the present invention has been discussed in detail in terms of the first to fourth embodiments of the present invention with reference to the accompanying drawings, such particular embodiment should not be taken as limitative for the technical scope of the present invention.