Hardware device for processing the tasks of an algorithm in parallel

CROSS-REFERENCE TO RELATED APPLICATIONS

0001The present application is a continuation application to U.S. application Ser. No. 11/322,378, filed on Jan. 3, 2006 now U.S. Pat. No. 7,383,311, which is a continuation application to U.S. application Ser. No. 09/606,899, filed on Jun. 29, 2000, now U.S. Pat. No. 6,999,994, the contents of both of which are herein incorporated by reference in their entireties.

TECHNICAL FIELD

0002The invention relates to processing of algorithms used in the search engines of a large data communication network such as the Internet, and relates more particularly to hardware devices for processing the tasks of any algorithm in parallel.

BACKGROUND

0003The World Wide Web (WWW) provides accesses to a large body of information. Compared with traditional databases, Web information is dynamic and structured with hyperlinks. Also, it can be represented in different forms and is globally shared over multiple sites and platforms. Hence, querying over the WWW is significantly different from querying data from traditional databases, e.g. relational databases, which are structured, centralized and static. Traditional databases can cope with a small number of information sources; but it is ineffective for thousands.

0004Most Web documents are text-oriented. Most relevant information is usually embedded in the text and can not be explicitly or easily specified in a user query. To facilitate Web searching, many search engines and similar programs have been developed. Most of these programs are database based meaning that the system maintains a database, a user searches the web by specifying a set of keywords and formulating a query to the database. Web search aids are variously referred to as catalogs, directories, indexes, search engines, or Web databases.

0005A search engine is a Web site on the Internet which someone may use to find desired Web pages and sites. A search engine will generally return the results of a search ranked by relevancy.

0006A competent Web search engine must include the fundamental search facilities that Internet users are familiar with, which include Boolean logic, phrase searching, truncation, and limiting facilities (e.g. limit by field). Most of the services try more or less to index the full-text of the original documents, which allows the user to find quite specialized information. Most services use best match retrieval systems, some use a Boolean system only.

0007Web search engines execute algorithms having internal processes which are repetitive tasks with independent entry data. A classical step by step processing of all processes and decisions on one entry data before processing the next entry data is inefficient since it takes too much time to process all the data. Thus, it is common to perform a search of a pattern within each file of a disk. The main repetitive processes to perform are: load file, open file, scan each word and compare for matching with a pattern, append the result in a temporary file, close file.

0008One way to improve the performance, and in particular to improve the search response time, is to achieve parallel processing by parallelizing the search mechanism in the database or index table. Such software parallelization will be more optimized but is nevertheless limited insofar as the software processing, even if parallelized, requires a minimum of time which cannot be reduced.

SUMMARY OF THE INVENTION

0009Accordingly, the object of the invention is to provide a hardware assist device able to run a set of repetitive processes using local pipelining for each task, and maintaining a relationship between the parent task and the child task for each occurrence in the pipeline.

0010Another object of the invention is to provide a hardware device for processing the tasks of a search algorithm in parallel wherein each specific task of the search is made by a dedicated processor.

0011The invention relates therefore to a hardware device for processing the tasks of an algorithm of the type comprising a number of processes the execution of some of which depend on binary decisions, the device comprising a plurality of task units which are each associated with a task defined as being either one process or one decision or one process together with the following decision, and a task interconnection logic block connected to each task unit for communicating actions from a source task unit to a destination task unit, each task unit including a processor for processing the steps of the associated task when the received action requests such a processing and a status manager for handling the actions coming from other task units and building the actions to be sent to other task units

BRIEF DESCRIPTION OF THE DRAWINGS

0012The above and other objects, features and advantages of the invention will be better understood by reading the following more particular description of the invention in conjunction with the accompanying drawings wherein:

0013<figref idref="DRAWINGS">FIG. 1</figref> represents an exemplary algorithm composed of three processes and three decisions.

0014<figref idref="DRAWINGS">FIG. 2</figref> represents the algorithm illustrated in <figref idref="DRAWINGS">FIG. 1</figref> which has been structured into several tasks to be executed by the hardware device according to the invention.

0015<figref idref="DRAWINGS">FIG. 3</figref> is a block-diagram representing the hardware device according to the invention.

0016<figref idref="DRAWINGS">FIG. 4</figref> is a representation of the configuration register used to control each task executed by the hardware device of <figref idref="DRAWINGS">FIG. 3</figref>.

0017<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> are tables representing respectively the actions to be executed by each task of the algorithm illustrated in <figref idref="DRAWINGS">FIG. 1</figref> in function of the possible activation sources for an instance and the following instance.

0018<figref idref="DRAWINGS">FIG. 6</figref> is a block-diagram representing the connection between the task interconnection logic block of the hardware device of <figref idref="DRAWINGS">FIG. 3</figref> and the different tasks of the algorithm.

DETAILED DESCRIPTION

0019The exemplary algorithm illustrated in <figref idref="DRAWINGS">FIG. 1</figref> includes three processes P₁, P₂and P₃and two decisions D₁and D₂. Depending on each decision, different functions corresponding to the different paths in the algorithm may be run. The first function is represented by the algorithm flow when decision D₁is “yes”, that is when processes P₁and P₂are to be executed. The second function is represented by the algorithm flow when decision D₁is “no” and decision D₂is “yes”, that is when processes P₁and P₃are to be executed. Finally, the third function is represented by the algorithm flow when decision D₁is “no” and decision D₂is also “no”, that is when only process P₁is to be executed. In the latter case, the algorithm flow loops back to the entry point and the same functions may be executed again. Thus, during the first algorithm flow, process P₁is started while the execution of process P₁is started again when decision D₂is “no”. The second execution of P₁starts only after the first execution of P₁has been completed and decision D₁and D₂have been completed. Therefore, there is no overlap possible in a simple step by step processing of the algorithm.

0020Though the algorithm represented in <figref idref="DRAWINGS">FIG. 1</figref> is very simple, all the algorithms are classically run in the same way. All the events (processes or decisions) of the algorithm flow have to be executed step by step although they are run repetitively with new entry data. The proposed invention allows the various processes and decisions to run separately in order to speed up the processing of the algorithm especially when there is no prior data required on some steps. The main idea to achieve this is to have one processor assigned to a task including a process, a decision or a combination of processes and decisions which will run all the repetitive instances of this task and will be linked to the execution result of the other task processors using a more detailed link information that the simple conventional link enabling the downstream tasks to be activated.

0021Using the principles of the invention, the algorithm of <figref idref="DRAWINGS">FIG. 1</figref> can be divided into tasks as illustrated in <figref idref="DRAWINGS">FIG. 2</figref>. Four tasks are thus implemented.

0022Task 1 (T₁) includes process P₂(no decision)

0023Task 2 (T₂) includes process P₃(no decision)

0024Task 3 (T₃) includes the sequential combination of process P₁and decision D₁

0025Task 4 (T₄) includes only decision D₂(no process)

0026According to the invention, each task is repetitively performed by one processor allocated to this task. Therefore, four processors will be required to run the example algorithm of <figref idref="DRAWINGS">FIG. 1</figref> and <figref idref="DRAWINGS">FIG. 2</figref>.

0027The hardware device according to the invention illustrated in <figref idref="DRAWINGS">FIG. 3</figref> comprises as many task units <b>10</b>, <b>12</b>, <b>14</b> as the number of tasks included in the algorithm (Task₁, Task₂. . . Task_n). The interconnection between the tasks is performed by the intermediary of a Task interconnection logic block <b>16</b> as explained hereafter.

0028Each task unit like task unit <b>10</b> includes a processor <b>18</b> in charge of processing the sequential steps of the process, the decision or the combination of the process and the decision generally incorporated in the corresponding task. Actions received from other task units or sent to other task units by means of Task interconnection logic block <b>16</b> are managed by status manager <b>20</b> which is preferably a state machine. Status manager <b>20</b> is connected to processor <b>18</b> by two lines, an input line to processor <b>18</b> for starting (S) the task execution and the output line from the processor which is activated when the task is completed (C).

0029Status manager <b>20</b> has essentially two functions (input and output). The input function handles incoming commands from other tasks and the output function builds commands to be sent to other tasks. To perform these functions in conjunction with processor <b>18</b>, several control/data registers <b>22</b>, <b>24</b>, <b>26</b> are used. Each control/data register corresponds, for this task, to an instance of the algorithm flow. The number of instances which can be run at the same time depends upon the pipeline capability of processor <b>18</b>. Generally, it is necessary to have three control/data registers corresponding to instances m, m+1, m+2.

0030Each control/data register <b>22</b>, <b>24</b> or <b>26</b> contains a control field and a data field. The control field is composed of three bits controlled by processor <b>18</b>, a validation bit V, a completion bit C and a bit L/R indicating whether the output is Left of Right when the task includes a decision.

0031The data field of a control/data register contains data which are loaded by status manager <b>20</b> after receiving an action to be performed from another task and before starting the task execution by sending the start command to task processor <b>18</b>. These data may be used by processor <b>18</b>. When the latter has completed the task execution, it may replace the data contained in the control/data register by other data. This data will then be sent to the destination task in the command word and used as an input field by the destination task processor. However, it must be noted that, in case of independent tasks, the data are not modified in the control/data register.

0032When the task execution has been completed by processor <b>18</b>, this one sets to 1 the bit C of the control field of the control data register and a signal C may be sent to status manager <b>20</b>. Therefore, either status manager is activated by the input signal C from task processor <b>18</b>, or there is a polling or an interrupt mechanism which enables the status manager to be informed of the setting of bit C to 1.

0033The commands which may be received from another task by status manager <b>20</b> are START, KILL or VALID. As already mentioned, the START command is used to activate task processor <b>18</b>. The KILL command means that a task is no longer of interest since the taken decision is opposite to this task. Thus, a task which is the left path of a decision may be killed if the decision is to take the right path. When it receives a KILL command, status manager <b>20</b> clears the control data register corresponding to the instance being considered as each command has as a parameter the instance value called level. Conversely to the KILL command, the VALID command confirms that the considered task corresponds to the taken decision. In such a case, the bit V of the corresponding control/data register is set to 1 by status manager <b>20</b>.

0034The output function of status manager <b>20</b> is to build commands based on the contents of two configuration registers, CONFIG.L <b>28</b> and CONFIG.R <b>30</b> and also on the contents of the involved control/data register. The contents of CONFIG.L register which is selected when bit L/R set to 1 are given in <figref idref="DRAWINGS">FIG. 4</figref>. Note that the CONFIG.R register which is selected when bit L/R is set to 0 has exactly the same structure as CONFIG.L register. Note that the CONFIG.L and CONFIG.R registers are loaded at the beginning of algorithm processing and remain unchanged insofar as they contain data fields depending only on the algorithm structure.

0035As illustrated in <figref idref="DRAWINGS">FIG. 4</figref>, CONFIG.L register contains a first block C selected when bit C is set to 1 and a second block V selected when bit V is set to 1. Each block C or V is used for two actions. For each action the register contains the three following fields wherein X=C or V and n=1 or 2.

0036Task Xn indicates which task should be activated

0037Axn indicates which action is to be performed. For example 00=kill, 01=start, 10=valid and 11=valid+start.

0038Lxn indicates the level of task (the instance) corresponding to Task Xn. For example, 00=current level−1, 01=current level, 10=current level+1, 11=current level+2.

0039The example of the algorithm illustrated in <figref idref="DRAWINGS">FIG. 2</figref> will be considered below. In <figref idref="DRAWINGS">FIG. 2</figref> there are four tasks T₁, T₂, T₃and T₄which can be executed, but there are six activation sources since Task 3 and Task 4 each have two outputs. Furthermore, a task acting as a source task can activate a destination task in the same level or in the following level. <figref idref="DRAWINGS">FIG. 5A</figref> and <figref idref="DRAWINGS">FIG. 5B</figref> represent tables wherein the activation sources are associated with the columns whereas the tasks to be activated are associated with the rows. <figref idref="DRAWINGS">FIG. 5A</figref> corresponds to the activation of the tasks in a same level whereas <figref idref="DRAWINGS">FIG. 5B</figref> corresponds to the activation of the tasks in level m+1 by activation sources in level m. It should be noted that since only two levels are represented, this means that there is no relationship between the processes of the algorithm on more than two consecutive levels.

0040In the tables illustrated in <figref idref="DRAWINGS">FIGS. 5A and 5B</figref>, only the cases corresponding to an action from an activation source to a task are filled with a letter. Letter S means Start, V means Validate and K means Kill. It must be noted that it is possible that a same source has an action on two tasks. Thus, T₃R kills Task 1, and starts and validates Task T₄.

0041As already mentioned, status manager <b>20</b> (<figref idref="DRAWINGS">FIG. 2</figref>) uses the control bits which have been previously loaded in CONFIG.L and CONFIG.R registers associated with the task. Thus, if we consider Task 3 which generates two activation sources, the CONFIG.L and CONFIG.R registers have the following contents:

CONFIG.L

0042<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>1. Block C</entry></row><row><entry /><entry>  Action 1 Task C₁=Task 3</entry></row><row><entry /><entry>    AC₁=start</entry></row><row><entry /><entry>    LC₁=current level+1</entry></row><row><entry /><entry>  Action 2 none</entry></row><row><entry /><entry>2. Block V</entry></row><row><entry /><entry>  Action 1 Task V₁=Task 1</entry></row><row><entry /><entry>    AV₁=valid</entry></row><row><entry /><entry>    LV₁=current level</entry></row><row><entry /><entry>  Action 2 none</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> CONFIG.R

0043<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>1. Block C</entry></row><row><entry /><entry>  Action 1 Task C₁=Task 3</entry></row><row><entry /><entry>    AC₁=start</entry></row><row><entry /><entry>    LC₁=current level+1</entry></row><row><entry /><entry>  Action 2 none</entry></row><row><entry /><entry>2. Block V</entry></row><row><entry /><entry>  Action 1 Task V₁=Task 1</entry></row><row><entry /><entry>    AV₁=kill</entry></row><row><entry /><entry>    LV₁=current level</entry></row><row><entry /><entry>  Action 2 Task V₂=Task 4</entry></row><row><entry /><entry>    AV₂=valid+start</entry></row><row><entry /><entry>    LV₂=current level</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0044The Task interconnection logic block <b>16</b> is represented in <figref idref="DRAWINGS">FIG. 6</figref>. Each task such as Task 1, Task 2, Task 3, . . . Task n is an input to Task interconnection logic block <b>16</b> but is also an output to this block. Each input action or command could be of the same type as each one of the output actions such as KILL, START or VALID. Using the CONFIG.L and CONFIG.R registers where an action is represented by three control fields Task Xn, Axn and Lxn, an action word may use this control fields in addition to the corresponding data (see <figref idref="DRAWINGS">FIG. 4</figref>) to transmit the action to the destination task.

0045In the preferred embodiment illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, the action word containing the control bits of CONFIG.L or CONFIG.R registers and data is input to a three-state driver <b>40</b>, <b>42</b>, <b>44</b> or <b>46</b> where the Task Xn field is decoded in order to select on which bus this action word should be put. This word, or the remaining bits insofar as the Task Xn field is no longer used, are then decoded by the appropriate task to perform the requesting action.

0046As illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, there are as many buses as the number of tasks. These buses are three-state so that all inactive inputs have no influence in the bus value. Only the valid one forced by the corresponding driver takes the bus for its command. The width of the bus depends on the size of the action word. In the preferred embodiment the bus size is equal to word size. If there is a problem in the size of the bus, it is well known how to split the word into several blocks appended when sent on a smaller bus. The only drawback of this split will be an increased transmission latency as it will need several clock times to transmit a command or action from one output task to an input task. At least, the Task Xn should be available in the first block of the split word to be decoded correctly.

0047Each task can then put all the actions on the various buses. As long as there is no capability to have an action simultaneously put on the same bus by two tasks, there is no arbitration required. This is the case for most of the algorithms. Otherwise, an arbitration mechanism may be added on the control of each three-state driver to identify two simultaneous requests for the same destination. A very simple contention mechanism will for example give the priority on the destination bus to the lower source task.