Parallel computer

• US 5,815,793 A
• Filed: 10/05/1995
• Issued: 09/29/1998
• Est. Priority Date: 10/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ferguson, Robert
• Primary Examiner(s): Lee, Michael
• Assistant Examiner(s): Lo, Linus H.
• Application Number:
  US08/539,399
• Time in Patent Office: 1,090 Days
• Field of Search: 348/12, 348/13, 348/6, 348/7, 348/8, 455/5.1, 455/6.1, 455/4.2, 455/6.2, 455/6.3, 455/3.1
• US Class Current: 725/131
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: H04N 21/443 OS processes, e.g. booting an STB, implementing a Java virtual machine in an STB or power management in an STB
• CPC Class Codes: H04N 7/173 with two-way working, e.g. subscriber sending a programme selection signal

Abstract

A massively parallel computer system employs hundreds or thousands of otherwise-idle microprocessors in set-top boxes distributed throughout a cable television system. Coupling between these processing nodes is effected by the cable television distribution network, which provides an asymmetrical transmission speed characteristic that is well suited for many parallel applications. The system is tolerant of interruptions due to preemption of set-top boxes for television viewing.

Claims

1. In a parallel processor including a control station coupled to a plurality of processing nodes, the control station serving to partition a processing task and distribute partitioned subtasks thereof to the processing nodes for processing, the control station further serving to collect processed results from said nodes and use said results to produce a final output to said processing task, an improvement comprising an asymmetrical network coupling each of the processing nodes to the control station, said network providing a first bandwidth link for coupling data from the control station to the processing nodes, and a second bandwidth link for coupling data from the processing nodes back to the control station, said first bandwidth being at least twice the second bandwidth, wherein the network resources are efficiently allocated to handle processing tasks that can be partitioned into subtasks which have more input data than output data.

2. The parallel processor of claim 1 in which different of said processing nodes are available at different times to receive partitioned subtasks of said processing task, due to occasional use of said nodes for other processing jobs, said other processing jobs being unrelated to said processing task, the scheduling of said other processing jobs not being under the control of the control station.

3. The parallel processor of claim 1 in which the network includes a wireless link for coupling data from the control station to the processing nodes.

4. The parallel processor of claim 1 in which the network includes a terrestrial link for coupling data from the processing nodes back to the control station.

5. The parallel processor of claim 1 in which the network includes nodes located in a plurality of different states.

6. The parallel processor of claim 1 in which a plurality of said nodes are set-top boxes usable in conjunction with cable television receivers.

7. The parallel processor of claim 1 in which said network further includes means for providing entertainment programming to nodes that are not provided subtasks of said processing task.

8. The parallel processor of claim 1 in which the same physical medium is used both to couple data from the control station to the processing nodes, and to couple data from the processing nodes back to the control station.

9. The parallel processor of claim 1 in which the plurality of processing nodes comprise plural cable television receivers, each television receiver including a processing unit, each television receiver having a first state in which the processing unit therein is performing a subscriber function for display of video to a user, and a second state in which said processing unit is not performing a subscriber function, the receiver including means for changing between the first and second states;

the parallel processor further including a plurality of distribution switches, each coupled to a plurality of said cable television receivers, and a central facility including mass storage means and a control processor, each of the distribution switches being coupled to said central facility, wherein a network comprising the distribution switches and the coupling between the central facility and the television receivers is asymmetrical in transmission speed, allowing data transmission to the television receivers from the central facility at a rate at least ten times that of data transmission to the central facility from the television receivers.

10. In a parallel processor including a control station coupled to a plurality of remote processing nodes, the control station serving to partition a processing task and distribute partitioned subtasks thereof to the processing nodes for processing, the control station further serving to collect processed results from said nodes and use said results to produce a final output to said processing task, an improvement wherein each of the processing nodes is switchable between primary and secondary modes of operation, in the secondary mode the node being available to process a subtask distributed thereto by the control station, in the primary mode the node being preempted from subtask processing by local usage of the node for a task unrelated to said processing task, said local usage not being invoked by the control station but being scheduled by a human user, and wherein each node includes means for automatically indicating to the control station if it is in said secondary mode of operation.

11. The parallel processor of claim 10 in which a plurality of said processing nodes comprise television set-top boxes.

12. The parallel processor of claim 10 in which the plurality of remote processing nodes comprise plural cable television receivers, each television receiver including a processing unit, in the primary mode each television receiver performing a subscriber function for display of video to a user, in the secondary mode each television receiver not performing a subscriber function.

13. The parallel processor of claim 12 in which each receiver includes means for changing between the primary and secondary modes;

the parallel processor further including a plurality of distribution switches, each coupled to a plurality of said cable television receivers, and a central facility including mass storage means and a control processor, each of the distribution switches being coupled to said central facility, the control processor including means for discerning whether each of said television receivers is in the secondary mode, the control processor further including means for partitioning a processing task into a plurality of subtasks, means for allocating said subtasks among processing units in said television receivers that have been discerned to be in the secondary mode, means for collecting processed data from said receivers into said mass storage to form a composite set of data results.

14. The processor of claim 13 in which the control processor further includes recovery means for recovering from a subtask interruption caused by a television receiver being changed from the secondary mode to the primary mode before completing a subtask allocated thereto.

15. The processor of claim 14 wherein a network comprising the distribution switches and the coupling between the central facility and the television receivers is asymmetrical in transmission speed, allowing data transmission to the television receivers from the central facility at a rate at least ten times that of data transmission to the central facility from the television receivers.

16. In a parallel processor including a control station coupled to a plurality of processing nodes, the control station serving to partition a processing task and distribute partitioned subtasks thereof to the processing nodes for processing, the control station further serving to collect processed results from said nodes and use said results to produce a final output to said processing task, an improvement comprising means responsive to human intervention at each of said nodes for preempting a processing subtask at said node that is in-process so as to perform a different processing job unrelated to said processing task, and wherein the control system includes means for redundantly distributing a plurality of said subtasks to at least two processing nodes so as to reduce delays in completing the processing task due to such preemptions.

17. The parallel processor of claim 16 in which the control system includes means for distributing each of said subtasks to at least two processing nodes.

18. The parallel processor of claim 16 in which a plurality of said processing nodes comprise television set-top boxes.

19. The processor of claim 16 in which the plurality of processing nodes comprise plural cable television receivers, each television receiver including a processing unit, the processing subtask being use of the television receiver for display of video to a user.

20. In a multi-processor system employing a central control processor linked to a plurality of distributed processors, the central processor serving to partition a processing task and distribute partitioned subtasks thereof to the distributed processors for processing, the control station further serving to collect processed results from said nodes and to use said results to produce a final output to said processing task, an improvement wherein:

each of said distributed processors is linked to the central control processor, but not with others of said distributed processors;

the system includes means for providing subtask data as well as control signals from the central control processor to each distributed processor;

the central control processor comprises circuitry different than each of the distributed processors; and

each link provides a first bandwidth path for coupling data from the central control processor to a distributed processor corresponding thereto, and provides a second bandwidth path for coupling data from said distributed processor back to the central control processor, the first bandwidth being at least twice the second.

21. The system of claim 20 in which at least one of said distributed processors has primary and secondary operating modes, the processing of said partitioned subtasks being the secondary operating mode and occurring only at times when said distributed processor is not engaged in the primary operating mode.

22. The system of claim 21 in which each of said plurality of distributed processors has said primary and secondary operating modes.

23. The multi-processor system of claim 20 in which the plurality of distributed processor comprise plural cable television receivers, each including a processing unit.

24. A remotely distributed processing system including:

a central facility;

a plurality of remotely distributed processing units, each unit being switchable between at least first and second modes, in the first mode the unit being unavailable to process a subtask assigned thereto by the central facility, in the second mode the unit being preempted from subtask processing by local usage of said unit, said local usage not being invoked by the central facility, each unit indicating its mode to the central facility;

a network coupling each processing unit to the central facility;

the central facility including means for partitioning a processing task into a plurality of subtasks, distributing said subtasks to remote processing units indicated as being in the first mode, and receiving subtask results back therefrom; and

completion means for completing processing of said processing task notwithstanding interruption of at least one subtask due to switching of a processing unit executing said subtask from the first mode to the second mode before execution of said subtask is completed.

25. The remotely distributed processing system of claim 24 in which the plurality of remotely distributed processing units comprise plural cable television receivers, each including a processing unit.

26. The system of claim 24 wherein the central facility further includes a database containing data related to patterns of local usage for said remote processing units.

27. The system of claim 24 in which the central facility includes a timer for each processing unit allocated a subtask, for sensing subtask interruption by failure of the processing unit to return subtask results data to the central facility within a timed interval.

28. The system of claim 24 in which the completion means includes means for allocating a given subtask to a plurality of different processing units for redundant processing, wherein interruption of a subtask does not unduly interrupt processing of said processing task.

29. The system of claim 28 which further includes means for comparing subtask results returned from at least two of said different processing units.

30. The system of claim 28 in which the central facility further includes a database containing data useful in determining how many different processing units to use in redundantly processing a given subtask, in view of patterns of local usage of said processing units.

31. The system of claim 24 in which the completion means includes reallocation means at the central facility for reallocating an interrupted subtask to a different, substitute processing unit.

32. The system of claim 31 in which said reallocation means includes means for providing restoration data from the central facility to the substitute processing unit to allow it to resume processing of the interrupted subtask from an intermediate state, rather than starting over.

33. The system of claim 31 in which the reallocation means includes means for reinitializing the substitute processing unit to start the interrupted subtask from the beginning thereof.

34. A remotely distributed processing system including a central facility and a plurality of remotely distributed processing units, each of the processing units being switchable between first and second modes, in the first mode the processing unit being available to process a subtask assigned thereto by the central facility, in the second mode the processing unit being preempted from subtask processing by local usage of the unit, said local usage not being invoked by the central facility, the central facility including means for partitioning a processing task into a plurality of subtasks, distributing said subtasks to processing units in the first mode, and receiving subtask results back therefrom, the central facility including a database containing data relating to historical patterns of local usage for said processing units, wherein said subtasks can be allocated among said processing units in accordance with said historical usage patterns.

35. The remotely distributed processing system of claim 34 in which the plurality of remotely distributed processing units comprise plural cable television receivers, each including a processing unit, said local usage of a remotely distributed processing unit comprising use of the cable television receiver to view video.

36. The system of claim 34 in which the central facility includes means for distributing a given subtask to a plurality of different processing units for redundant processing, wherein interruption of a subtask by switching of a processing unit to the second mode prior to execution of a subtask distributed thereto does not unduly interrupt processing of the processing task.

37. The system of claim 36 which includes means for determining the number of redundant processing units in accordance with historical usage data stored in the database.