Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-09-09
2001-12-11
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S241000, C712S029000, C712S030000, C710S261000, C710S264000
Reexamination Certificate
active
06330583
ABSTRACT:
This invention relates to computer networks, and more particularly, to a distributed parallel processing network system wherein a large compute-intensive task may be partitioned into subtasks which are then distributed among a plurality of personal computer or workstations for parallel execution of the subtasks in the background concurrently with the execution in the foreground of the respective local tasks of the individual workstations.
The disclosed computers of the present invention may be either those designated by the term “workstations” or those designated by the term “personal computers”. In the present specification and claims these terms may be regarded as synonymous, since the invention operates in the same manner with both categories of computer. Several of the claims utilize the coined term “personal computer workstations” which is to be understood as generic to include both categories.
BACKGROUND OF THE INVENTION
In the conventional local area network comprising a plurality of interconnected workstations or personal computers most of the execution time and processing power of the computers are wasted while waiting idly for slow input/output devices. For example, in the time intervals between successive keystrokes at the keyboard a central procesing unit would be able to execute thousands of instructions if there were some way to put the unit to use instead of compelling it merely to wait for the next keystroke. Other input/output operations such as mouse movements, printing tasks and disk drive activities are similarly many orders of magnitude slower than CPU (central processing unit) operations and result in a further waste of much of the running time and computational power of the computer. Furthermore, when the CPU eventually does get the opportunity to process a keystroke code, mouse movement, printer command or disk access the CPU can finish its share of the input/output task relatively quickly so that the unit is soon back to its idle waiting state. Also, at any typical instant some of the workstations may not be operated by the respective users, thereby further contributing to the waste of computer time and power.
Another problem with conventional local area network systems is that each individual workstations or personal computer lacks the power to execute within a reasonable time those large compute-intensive applications which frequently arise in science, engineering, financial analysis, image processing and other fields. Heretofore such applications required processing either by mainframes or by network servers accessed by remote procedure calls in an expensive distributed computing environment.
OBJECTS OF THE INVENTION
It is therefore a primary object of the present invention to provide a distributed parallel processing network system which utilizes the otherwise wasted execution time and computation power of the workstations or personal computers by enabling their CPUs to perform in the background parallelized compute-intensive tasks, while concurrently peforming their local individual tasks in the foreground without any slowdown perceptible to the users.
It is a further object of the invention to provide a system wherein a network of workstations or personal computers may operate in parallel to form a powerful multicomputer system for parallel processing of large time-consuming compute-intensive applications in a fraction of the time that it would take any of the individual computers to do the job alone.
SUMMARY OF THE INVENTION
The preferred embodiment of the invention, disclosed herein as illustrative of one of the many forms which the invention may take in practise, comprises a network of interconnected workstations or personal computers each having the usual console including a keyboard and a CRT (cathode ray tube) monitor display for interactive operation by a user to perform a respective local task on each computer. Most of these local tasks are either input/output intensive or of relatively small size.
If a computer has a task which is both large and compute-intensive, the task is partitioned into a plurality of smaller subtasks to be executed simultaneously in parallel by the other computers of the network. Each of these subtasks is assigned its respective identifier. One of the network disk drives has a directory constituting a pool for storing all of the subtask identifiers, preferably in the form of a queue. Each of the other computers of the network selects a subtask identifier from the pool, copies the corresponding subtask program from the originating computer, executes the selected subtask in the background while concurrently executing its own local task in the foreground, returns the computed results of the subtask computation to the originating computer, and then selects another subtask from the pool to repeat the cycle.
Each workstations or personal computer of the network operates in a preemptive multitasking mode controlled by a clock, tick counter, interrupt controller and scheduler. The clock periodically generates ticks which are tallied by the counter until the count reaches a predetermined number of ticks equal to a timeslice of about 20 milliseconds. The counter then activates the interrupt controller which in turn activates the interrupt input pin of the CPU (central processing unit). This initiates a CPU interrupt operation which terminates the current timeslice of execution. The currently executing task is interrupted and preempted, and control of the CPU is taken away from the preempted task and passed to an interrupt service routine which contains or invokes the scheduler.
The scheduler then transfers control of the CPU to the next task to be executed during the next timeslice. If the preempted task had been a local task then the scheduler will pass control of the CPU to a remote subtask which is concurrently executing in the background. If no remote subtask is being concurrently executed then the computer searches the network directory pool for the next subtask identifier waiting in the queue, copies from the originating computer the subtask program corresponding to said next identifier, and then proceeds with the execution of this remote subtask. In either event, execution of the present subtask or a new subtask proceeds until preempted by the next interrupt terminating the new timeslice. If no remote subtask is being concurrently executed and the pool of subtask identifiers is empty then the new timeslice is aborted and control of the CPU is returned to the scheduler. Upon the termination of a timeslice of execution of a remote subtask the scheduler passes control of the CPU to the local task running interactively with the user in the foreground for execution during the next timeslice.
This preemptive multitasking mode of operation thus provides for each computer of the network a plurality of series of timeslices of execution, with the timeslices of each series interleaved with the timeslices of at least one other series. One series may consist of timeslices of execution of a local task in the foreground, and another series may consist of timeslices of execution of a remote subtask in the background, with the two series mutually interleaved so that control of the CPU of each computer switches back and forth between its respective local task and its respective remote subtask. This switching occurs so rapidly that each computer executes its respective local task concurrently and effectively simultaneously with its respective remote subtask. The plurality of computers of the network also execute simultaneously and in parallel with respect to each other. Each workstations user perceives no substantial delay in the interactive foreground execution of his own local task notwithstanding that his computer along with others in the network are concurrently executing remote parallel subtasks in the background.
The term “foreground” in the specification and claims is used in its ordinary sense generally understood by those skilled in the computer art to mean a mode of operation in which an executing process is visibly interact
LandOfFree
Computer network of interactive multitasking computers for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer network of interactive multitasking computers for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer network of interactive multitasking computers for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593103