(12) United States Patent
`Reiffin
`
`USOO6330583B1
`US 6,330,583 B1
`(10) Patent No.:
`Dec. 11, 2001
`(45) Date of Patent:
`
`(54) COMPUTER NETWORK OF INTERACTIVE
`MULTITASKING COMPUTERS FOR
`PARALLEL PROCESSING OF NETWORK
`SUBTASKS CONCURRENTLY WITH LOCAL
`TASKS
`
`(76) Inventor: Martin Reiffin, 5439 Blackhawk Dr.,
`Danville, CA (US) 94506
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 08/303,763
`(22) Filed:
`Sep. 9, 1994
`(51) Int. Cl. ................................ G06F 9/38; G06F 9/40;
`G06F 9/48; G06F 9/50
`(52) U.S. Cl. .......................... 709/105; 709/106; 709/107;
`709/108; 712/29; 712/30; 710/261; 710/264
`(58) Field of Search .................................. 712/28, 32, 13,
`712/18, 29, 30, 14, 228, 37,90, 31; 709/102,
`106, 103, 107, 104, 105, 108, 201, 400,
`205, 213, 226, 214, 215, 1, 101, 217, 251;
`710/20, 129, 261, 266, 264
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5/1980 Boyd .................................... 395/750
`4.203,153
`2/1984 Segara et al. ..
`395/200.03
`4,430,699
`8/1984 Advani et al. ....................... 395/275
`4,466,065
`10/1985 Baunach et al. .................. 364/419.1
`4,545,015
`8/1988 Konopik et al. ...
`... 395/275
`4,768,149
`4,879,733 * 11/1989 Burch et al. ........................... 377/44
`4,925,311 * 5/1990 Neches et al. .
`... 395/650
`4,949,254 * 8/1990 Shorter .......
`... 364/200
`5,001,666
`3/1991 Thompson et al.
`... 395/775
`5,062,037 * 10/1991 Shorter et al. .....
`... 395/200
`5,063,500 * 11/1991 Shorter .......
`... 395/200.03
`5,121,327
`6/1992 Salazar ............................ 364/464.02
`
`5,247,677 * 9/1993 Welland et al. ..................... 395/650
`5,295,264
`3/1994 Werres et al. ........................ 709/103
`5,347,477 * 9/1994 Lee ...............
`... 708/141
`5,386,561 * 1/1995 Huynh et al. ........................ 709/103
`5,402,350 * 3/1995 Kline ........
`364/468.07
`5,428,783
`6/1995 Lake ..................................... 709/106
`5,428,789 * 6/1995 Waldron, III ........................ 709/213
`5,469,549 * 11/1995 Simpson et al. ..................... 709/213
`5,606,493 * 2/1997 Duscher et al. .
`. 364/134
`5,694,603 * 12/1997 Reiffin ..........
`... 709/107
`5,694,604 * 12/1997 Reiffin ...
`... 709/107
`5,799,320 * 8/1998 Klug.
`... 707/201
`5,978,832
`11/1999 Sirkin ................................... 709/107
`
`OTHER PUBLICATIONS
`Microsoft Press Computer Dictionary, pp. 34,217, 266,313,
`Nov. 10, 1993.*
`* cited by examiner
`Primary Examiner Daniel H. Pan
`(57)
`ABSTRACT
`A local area computer network provides distributed parallel
`processing. The network comprises a plurality of WorkSta
`tions or personal computers, each having preemptive mul
`titasking for the interactive execution of a local task in the
`foreground concurrently with a remote network Subtask in
`the background. A large compute-intensive task may be
`partitioned into a plurality of parallel Subtasks executed
`Simultaneously with each Subtask executed in the back
`ground by a respective WorkStations without Substantial
`interference with the local task being executed concurrently
`in the foreground. The computer time and processing power
`which would otherwise be wasted while waiting for slow
`input/output operations is instead utilized to provide a
`powerful parallel multiprocessor System for handling
`compute-intensive tasks too large for an individual work
`Stations.
`
`10 Claims, 4 Drawing Sheets
`
`
`
`CENTRA
`ce PROCESSING
`UNIT
`
`
`
`
`
`
`
`
`
`
`
`SCHEDULER
`
`
`
`NTERRUPT
`CONTROLLER
`
`AA/SWA Ex. 1004, p.1 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`U.S. Patent
`
`Dec. 11, 2001
`
`Sheet 1 of 4
`
`US 6,330,583 B1
`
`FIG. 1
`
`
`
`
`
`
`
`
`
`WORK
`STATION
`1
`
`
`
`WORK
`STATION
`2
`
`
`
`
`
`WORK
`STATION
`N
`
`CONSOLE
`
`CONSOLE
`
`CONSOLE
`
`FIG 2
`
`CENTRAL
`D PROCESSING
`UNIT
`
`W
`
`
`
`
`
`INTERRUPT
`CONTROLLER
`
`NETWORK
`TASK
`
`SCHEDULER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`AA/SWA Ex. 1004, p.2 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`U.S. Patent
`
`Dec. 11, 2001
`
`Sheet 2 of 4
`
`US 6,330,583 B1
`
`CLOCK TICK
`COUNTER
`
`
`
`PREEMPTIVE
`NTERRUPT
`
`
`
`
`
`TASK
`SCHEDULER
`
`NEXT TASK
`TO RUN12
`
`FIG 3
`
`NETWORK
`TASK
`
`AA/SWA Ex. 1004, p.3 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`U.S. Patent
`
`Dec. 11, 2001
`
`Sheet 3 of 4
`
`US 6,330,583 B1
`
`FG. 4
`
`RESUME
`EXECUTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PROCESS
`MESSAGE TO SCHEDULER
`
`EXECUTION
`COMPLETED?
`
`TO SCHEDULER
`
`TIMESLICE
`TERMINATED
`
`TO SCHEDULER
`
`AA/SWA Ex. 1004, p.4 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`U.S. Patent
`
`Dec. 11, 2001
`
`Sheet 4 of 4
`
`US 6,330,583 B1
`
`
`
`NETWORK
`TASK
`
`FIG. 5
`
`
`
`
`RESUME
`EXECUTION
`
`TASK IN
`POOL12
`
`TO SCHEDULER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXECUTION
`COMPLETED2
`
`TIMESLCE
`TERMINATED
`
`TO SCHEDULER
`
`TO SCHEDULER
`
`AA/SWA Ex. 1004, p.5 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`US 6,330,583 B1
`
`1
`COMPUTER NETWORK OF INTERACTIVE
`MULTITASKING COMPUTERS FOR
`PARALLEL PROCESSING OF NETWORK
`SUBTASKS CONCURRENTLY WITH LOCAL
`TASKS
`
`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 man
`ner 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 cat
`egories.
`
`15
`
`25
`
`BACKGROUND OF THE INVENTION
`In the conventional local area network comprising a
`plurality of interconnected WorkStations or personal com
`puters 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 key
`Stroke. 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 fre
`quently arise in Science, engineering, financial analysis,
`image processing and other fields. Heretofore Such applica
`tions required processing either by mainframes or by net
`work 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 comput
`ers 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.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 com
`puter. 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 origi
`nating 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 pro
`cessing 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.
`
`AA/SWA Ex. 1004, p.6 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`US 6,330,583 B1
`
`15
`
`25
`
`35
`
`3
`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 effec
`tively 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 interacting with the
`user, So that the proceSS has control of the console and
`responds to commands issued from the keyboard or other
`interactive input device. Conversely, the term “background'
`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
`not visibly interacting with the user and is without control of
`the interactive input/output devices, and that Some other
`process is executing in the foreground.
`DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram showing the overall network
`comprising a plurality of interconnected WorkStations or
`personal computers,
`FIG. 2 is a block diagram showing for each of the
`40
`computers the relation between the relevant hardware com
`ponents comprising the CPU, clock, counter and interrupt
`controller, and the relevant executable Software components
`comprising the Scheduler, local task and network task,
`FIG. 3 is a flow chart showing the Sequence of operations
`Starting with the clock and extending to the execution of the
`local and network tasks alternately Selected by the Sched
`uler,
`FIG. 4 is a flow chart showing the further sequence of
`operations when the Scheduler proceeds to Select the local
`task for execution; and
`FIG. 5 is a flow chart showing the further sequence of
`operations when the Scheduler proceeds to Select a network
`task for execution.
`
`45
`
`50
`
`DETAILED DESCRIPTION
`Referring first to FIG. 1, this is a block diagram depicting
`an LAN (local area network) of interconnected computers
`which may be either WorkStations or personal computers.
`The network may be either a peer-to-peer type or a client
`Server type. Each computer comprises a console including a
`keyboard and a CRT display monitor for interactive opera
`tion of the computer by the respective user. For Simplicity in
`illustration, the computers are shown connected in Series by
`a single linear cable, as in an ethernet System, but any other
`conventional arrangement Such as a token ring topology may
`be employed instead.
`
`55
`
`60
`
`65
`
`4
`Referring now to FIG. 2, this is a block diagram showing
`the relation of the relevant hardware and Software compo
`nents of each computer of the network. In FIG. 3 there is
`shown a flowchart of the Overall Sequence of operations of
`these components. A clock periodically emits timing pulses
`or ticks at a fixed high frequency. A counter tallies the clock
`ticks until the total reaches a predetermined number which
`determines the time duration of each timeslice. This
`timeslice duration is preferably about 20 milliseconds.
`When the end of the current timeslice is thereby determined
`by the counter the latter then Signals the interrupt controller
`which in turn activates the interrupt input of the CPU
`(central processing unit) to initiate an interrupt operation.
`This causes the contents of the CPU registers to be stored
`in memory and control of the CPU is taken away from the
`executing task which is thereby asynchronously preempted.
`Control of the CPU is then passed to an interrupt service
`routine which contains or invokes the Scheduler for a
`determination as to the next task to be executed. If the just
`preempted task had been a local task the Scheduler will
`proceed to Select a network task as the next one to be
`executed, and conversely, if the preempted task had been a
`network task then the Scheduler will proceed to Select a local
`task. The term “local task” refers to a task which is executed
`Solely by a respective individual computer independently of
`the network. The term “network task” refers to a task which
`is originated by one computer of the network for distribution
`to and execution by other computers of the network. For
`example, a network task may be a Subtask resulting from the
`partition of a large compute-intensive task into many Sub
`tasks for parallel processing by a plurality of the network
`WorkStations.
`The scheduler signals its task selection to the CPU which
`then normally executes either the Scheduled local task or the
`Scheduled network task, as determined by the Scheduler, for
`the next Successive timeslice. At the Start of the next
`timeslice the counter is reset and the above-described cycle
`of operation is iterated over and over again as long as the
`computer remains in operation with local and network tasks
`still to be executed.
`The repeated activation of the interrupt operation thereby
`creates at least two Series of timeslices of execution, with the
`timeslices of one Series interleaved with the timeslices of at
`least one other Series. During each timeslice of one Series a
`local task is given control of the CPU and is executed
`piecemeal to perform a Successive portion of the local task,
`while interleaved with this piecemeal execution of the local
`task are the Successive timeslices of another Series during
`each timeslice of which a Successive portion of a network
`task is executed piecemeal. That is, control of the CPU is
`rapidly Switched back and forth between a local task and a
`network task So rapidly that the two tasks are said to be
`running concurrently and effectively simultaneously. A user
`operating interactively with his workStations console may
`thus run a local task in the foreground, while concurrently in
`the background a network task is being executed without the
`user's awareneSS. Generally this occurs without any percep
`tion by the user that his interactive foreground task is being
`Substantially delayed by this multitasking.
`This background execution of network tasks is particu
`larly Suited for the parallel multiprocessing of large
`compute-intensive programs which frequently arise in
`Science, engineering, financial analysis, graphics and other
`fields. The WorkStations or personal computer originally
`given Such a task may partition the data and program code
`into a plurality of Subtasks. A plurality of Subtask identifiers
`corresponding to the partitioned Subtasks are Stored in a
`
`AA/SWA Ex. 1004, p.7 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`S
`network directory of a disk drive of one of the computers to
`constitute a pool or queue identifying remote Subtasks to be
`executed. AS explained in more detail below, each computer
`of the network may access this pool, Select a Subtask
`identifier, copy the corresponding remote Subtask from the
`originating computer, execute the Subtask in the background
`without Substantial delay of its local processing, and return
`the computed Subtask results to the originating computer.
`AS a result most of the computer time and processing
`power of the entire network which would otherwise be
`wasted while waiting for Slow input/output operations is
`instead put to valuable use in the form of a powerful parallel
`multiprocessing System able to handle tasks which would
`overwhelm an individual WorkStations or personal computer.
`For example, if a very large matrix of floating point numbers
`is required to be processed, the matrix may be partitioned by
`rows and/or columns into a pluralty of Submatrices each of
`which, together with a Subprogram of processing code,
`would constitute a Subtask, So that a plurality of the network
`computerS may each process a respective one of the Sub
`matrices in parallel with the processing of the other Subma
`trices by other computers of the network.
`Referring now to FIG. 4, this is a flow chart showing the
`further Sequence of operations which occurs when the
`Scheduler of a particular computer proceeds to Select its
`respective local task for execution during the next timeslice.
`The decision block with the legend ACTIVE TASK'? rep
`resents a determination as to whether there is presently any
`local task which is concurrently being executed. If this
`determination is affirmative then the execution of this local
`task is resumed during the next timeslice. If this determi
`nation is negative then the message queue is checked for the
`presence of a message, as indicated by the decision block
`marked MESSAGE IN QUEUE? If a message is present it
`is processed during the next timeslice. If no message is
`waiting in the message queue control is returned to the
`scheduler which then proceeds to pass control of the CPU to
`a network task, as will be described below in connection
`with FIG. 5.
`The resumed execution of the previously active local task
`or the execution invoked by the processed message contin
`ues until either the execution is completed or is preempted
`by the next activation of the interrupt operation. If the
`execution of the local task is completed before the next
`interrupt activation the control of the CPU is returned to the
`Scheduler. Otherwise execution continues until the interrupt
`operation is activated to terminate the timeslice and return
`control of the CPU to the scheduler. The local task is thereby
`preempted but will eventually resume execution during a
`Subsequent timeslice.
`Referring now to FIG. 5, this is a flow chart showing the
`further Sequence of operations which occurs when the
`Scheduler proceeds to Select a network task for execution
`during the next timeslice. AS explained above, this network
`task may be a remote Subtask originating from the partition
`of a large compute-intensive task by another computer of the
`network. The decision block marked with the legend
`ACTIVE TASK'? represents a determination as to whether
`there is a network task presently running. If the determina
`tion is affirmative then execution of this network task is
`resumed for the next timeslice.
`If the determination is negative then the pool of Subtask
`identifiers is checked to determine if there is a remote
`Subtask or other network task waiting for execution, as
`indicated by the decision block marked TASKIN POOL? If
`the pool contains a task identifier then the latter is removed
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,330,583 B1
`
`6
`from the pool. If the network is a peer-to-peer type the
`network task corresponding to the identifier is copied from
`the disk drive of the other workstations which originally
`placed the network task in the pool, as indicated by the
`legend FETCH TASK. If the network is a client-server type
`then both the Subtask identifier pool and the Suprograms
`constituting the Subtasks are Stored on a Server computer and
`the Subtasks are fetched from the latter. The fetched remote
`Subtask or other network task is then executed. The com
`puted results from the execution of each Subtask are placed
`into files which are stored in a network directory which may
`be accessed by the WorkStations which originally partitioned
`and distributed the compute-intensive task.
`Execution of either the resumed network task or the newly
`fetched network task continues until either the task is
`completed or, as is more usually the case, the task is
`preempted by the termination of the timeslice at the next
`activation of the interrupt operation. Control of the CPU is
`then returned to the scheduler. The cycle of operation
`described above is then repeated over and over again by each
`workstations (or personal computer) for So long as the
`computer remains in operation with local and network tasks
`to be executed.
`The preferred embodiment of the invention disclosed
`herein is merely illustrative of one of the many forms which
`the invention may take in practise without departing from
`the Scope of the invention as delineated in the appended
`claims which are to be construed as broadly as permitted by
`the prior art.
`I claim:
`1. A computer network System for parallel computation
`and comprising
`a network of interconnected personal computer worksta
`tions each having means for executing a respective
`local task,
`at least one of Said personal computer WorkStations hav
`ing Stored therein a compute-intensive program and
`having means for partitioning Said compute-intensive
`program into a plurality of remote Subtasks for execu
`tion by other computers of Said network,
`Said personal computer WorkStations each having means
`for executing a respective one of Said remote Subtasks
`in parallel with the execution of the other remote
`Subtasks by the other computers,
`each of Said personal computer WorkStations including:
`(1) a central processor having an interrupt operation,
`(2) a clock timer for periodically activating said inter
`rupt operation at brief predetermined time-sliced
`intervals So as to asynchronously interrupt the execu
`tion of an executing task and to take therefrom
`control of the central processor upon each Said
`activation of Said interrupt operation, and
`(3) an interrupt Service routine responsive to each said
`clock timer activation of Said interrupt operation for
`passing control of the central processor to another
`task for execution of the latter,
`Said clock timer, interrupt operation and interrupt Service
`routine of each computer coacting to Switch control of
`the respective central processor repeatedly back and
`forth between a local task and a remote Subtask So
`rapidly that the respective local task and remote Subtask
`execute effectively simultaneously.
`2. A System as recited in claim 1 wherein
`each of Said personal computer WorkStations comprises
`means for the execution of a respective local task in the
`foreground during each timeslice of a first Series of
`
`AA/SWA Ex. 1004, p.8 of 9
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00785
`
`

`

`US 6,330,583 B1
`
`7
`Spaced timeslices while concurrently there with a
`respective one of Said Subtasks is executed in the
`background during each timeslice of a Second Series of
`Spaced timeslices interleaved with Said first Series of
`timeslices.
`3. A System as recited in claim 1 wherein
`each of Said computerS has a keyboard and a display
`monitor for interactive operation by a user,
`each Said local task being executed interactively with the
`user in the foreground while concurrently therewith the
`respective Subtask is being executed in the background,
`each Said preemptive multitasking means rapidly Switch
`ing execution of the computer back and forth between
`Said foreground task and Said background Subtask So
`that the foreground task and background Subtask are
`effectively executed Simultaneously and So that during
`the interactive eXecution of the foreground task the user
`perceives no Substantial delay or interference from the
`concurrent execution of the background Subtask.
`4. A System as recited in claim 1 and comprising
`a network directory for Storing files accessible by other
`computers of the network,
`Said partitioning means including means for Storing each
`of Said Subtasks as a file in Said network directory,
`each computer having a disk drive and means for copying
`a subtask file from said network directory and into the
`respective disk drive of Said computer.
`5. A system as recited in claim 1 wherein
`Said network comprises a disk drive having a file includ
`ing a pool of Subtask identifiers,
`Said partitioning means including means for Storing in
`Said pool an identifier corresponding to each Said
`Subtask,
`each computer including means responsive to the comple
`tion of execution of a Subtask to Select for execution a
`new Subtask from Said pool.
`6. A computer network system for distributed parallel
`computation concurrently with local computation, Said SyS
`tem comprising
`a network of interconnected computers each including:
`(1) a microprocessor having an interrupt input,
`(2) clock driven means for periodically activating said
`interrupt input at brief predetermined time intervals
`So as to asynchronously interrupt the execution of an
`executing task upon each activation of Said interrupt
`input,
`(3) an interrupt Service routine for preemptively taking
`control of the microprocessor in response to each
`Said activation of Said interrupt input and including
`means for passing control of the microprocessor to
`another task,
`(4) operator actuated means for interactively control
`ling the execution of a program task, and
`(5) display means for interactively showing to the
`operator effects of Said interactive control by Said
`operator actuated means,
`whereby a task of a program may execute interactively
`with the operator in the foreground while another task
`executes in the background concurrently with the inter
`active execution of the foreground task,
`at least one of Said computers having a program Stored
`therein,
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`8
`means for partitioning Said program into a plurality of
`remote tasks for execution by other computers of the
`network,
`means for transferring each of Said remote tasks to a
`respective computer of the network,
`each of Said computers having means for executing its
`respective remote task in parallel with the execution of
`the other remote tasks by the other computers,
`each of Said remote tasks being executed by its respective
`computer as a background task while concurrently
`there with the computer executes a respective local task
`in the foreground interactively with the operator,
`Said clock driven means and interrupt Service routine of
`each computer coacting to constitute a preemptive
`multitasking means for Switching control of the micro
`processor repeatedly between the foreground local task
`and the background remote task So rapidly that an
`interactive operator perceives the local task to be
`executing without delay or interference by the execu
`tion of the respective remote task in the background.
`7. A system as recited in claim 6 wherein
`each of Said preemptive multitasking means provides for
`the execution on each computer of a respective local
`task in the foreground during each timeslice of a first
`Series of Spaced timeslices while concurrently there
`with a respective one of Said Subtasks is executed in the
`background during each timeslice of a Second Series of
`Spaced timeslices interleaved with Said first Series of
`timeslices.
`8. A system as recited in claim 6 wherein
`each of Said computerS has a keyboard and a display
`monitor for interactive operation by a user,
`each said local task being executed interactively with the
`user in the foreground while concurrently therewith the
`respective Subtask is being executed in the background,
`each Said preemptive multitasking means rapidly Switch
`ing execution of the computer back and forth between
`Said foreground task and Said background Subtask So
`that the foreground task and background Subtask are
`effectively executed Simultaneously and So that during
`the interactive eXecution of the foreground task the user
`perceives no Substantial delay or interference from the
`concurrent execution of the background Subtask.
`9. A System as recited in claim 6 and comprising
`a network directory for Storing files accessible by the
`other comput