Scheduling and management in a personal datacenter

• US 9,268,613 B2
• Filed: 12/20/2010
• Issued: 02/23/2016
• Est. Priority Date: 12/20/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Barham, Paul, Figueroa, Joseph N.
• Primary Examiner(s): Kim, Sisley
• Application Number:
  US12/972,563
• Publication Number:
  US 20120159506A1
• Time in Patent Office: 1,891 Days
• Field of Search: 718/104
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A personal datacenter system is described herein that provides a framework for leveraging multiple heterogeneous computers in a dynamically changing environment together as an ad-hoc cluster for performing parallel processing of various tasks. A home environment is much more heterogeneous and dynamic than a typical datacenter, and typical datacenter scheduling strategies do not work well for these types of small clusters. Machines in a home are likely to be powered on and off, be removed and taken elsewhere, and be connected by an ad-hoc network topology with a mix of wired and wireless technologies. The personal data center system provides components to overcome these differences. The system identifies a dynamically available set of machines, characterizes their performance, discovers the network topology, and monitors the available communications bandwidth between machines. This information is then used to compute an efficient execution plan for data-parallel and/or High Performance Computing (HPC)-style applications.

Claims

1. A computer-implemented method for providing parallel processing in a heterogeneous personal computing environment, the method comprising:

determining one or more available computing resources in the computing environment by gathering information related to one or more computing resources actively connected to a personal network wherein determining further comprises determining if a device is a candidate to leave the computing environment based upon a current time and a historical entry and exit of the device to the personal network and categorizing that device as an unavailable computing resource when it is determined the device is the candidate to leave the computing environment;

running one or more benchmarks on the determined available computing resources to determine available capabilities that can be used for distributed computing;

receiving a job from an originating computing resource for execution on one or more other computing resources;

determining a schedule of one or more tasks for completing the job, wherein the tasks can be distributed to various available computing resources in the computing environment and the determined schedule selects a resource for each task that satisfies one or more performance criteria;

sending information describing each task to an available computing resource to perform the task;

managing each task to completion and gathering individual task results for the job; and

reporting the job results to the originating computing resource,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein determining one or more available computing resources comprises identifying one or more desktop computers, laptop computers, tablet computers, mobile phones, media computers, home servers, and game consoles connected via one or more networks in a home.

3. The method of claim 1 wherein determining one or more available computing resources comprises electing not to use resources that are currently in use by a user.

4. The method of claim 1 wherein running one or more benchmarks comprises querying an operating system on each computing resource to identify static and dynamic properties of the resource.

5. The method of claim 1 wherein running one or more benchmarks comprises periodically re-running benchmarks to update a central data store with information about each computing resource'"'"'s availability for scheduling the resource to perform tasks.

6. The method of claim 1 wherein receiving the job comprises receiving a job that will complete faster by utilizing multiple computing resources rather than the originating computing resource alone.

7. The method of claim 1 wherein receiving the job comprises receiving metadata that identifies one or more demands of the job that affects how the job is scheduled to available computing resources.

8. The method of claim 1 wherein determining the schedule comprises optimizing the job to complete quickly by matching demands of tasks of the job to capabilities of available computing resources.

9. The method of claim 1 wherein the performance criteria include avoiding over utilizing computing resources with a current interactive user.

10. The method of claim 1 wherein the performance criteria include identifying a schedule likely to complete in a fastest possible time.

11. The method of claim 1 wherein said sending information describing each task comprises providing a process for each computing resource to execute or instructions for a process already available on the computing resource to execute to perform the task.

12. A computer system for managing a heterogeneous personal datacenter, the system comprising:

a processor and memory configured to execute software instructions embodied within the following components;

a namespace component that manages a shared file system namespace between multiple computers in the personal datacenter;

a process execution component that manages execution of processes on each computing resource, wherein each process represents a subdivision of a larger job managed by the system;

a cluster resource manager that stores information describing available computing resources and ongoing distributed jobs that are executing on available computing resources in the personal datacenter;

a resource identification component that identifies computing resources in a personal data center environment that are available for performing distributed, parallel computing tasks, wherein an available computing resource is considered to be unavailable based upon a current time and a historical entry and exit of the device to the personal network and categorizing that device as an unavailable computing resource when it is determined that the available computing resources may soon leave the personal datacenter;

a benchmark component that determines one or more capabilities of each identified computing resource;

a job scheduling component configured to determine a schedule for completing a computing job by analyzing the identified computing resources, the determined capabilities of each computing resource, and one or more demands of the computing job; and

a job management component that manages execution of one or more tasks that make up a job on computing resources specified by the determined schedule.

13. The system of claim 12 wherein the process execution component includes a service or daemon running on each available computing resource in the personal datacenter that receives instructions from the job scheduling component to execute part of a job on the computing resource where the service is running.

14. The system of claim 12 wherein the cluster resource manager location is selected that is likely to remain available even as the datacenter environment changes.

15. The system of claim 12 wherein the resource identification component identifies one or more resources that include any of a central processing unit (CPU), graphics processing unit (GPU), memory, storage space, or other resources that can be leveraged to perform computing tasks or store data used in performing computing tasks.

16. The system of claim 12 wherein the benchmark component determines an availability schedule based on historical entry and exit of a computing resource into and out of the personal datacenter.

17. The system of claim 12 wherein the job scheduling component performs analysis of the job to identify at least one of the job'"'"'s likely processing demands, disk usage, memory usage, and communication.

18. The system of claim 12 wherein the job scheduling component divides a job into one or more tasks that can be executed by the available computing resources, wherein each task is an independent task that can be performed in parallel and completed on a single computing resource.

19. The system of claim 12 wherein the job scheduling component divides a job into one or more tasks and identifies one or more dependencies between tasks.

20. A computer-readable storage medium comprising instructions for controlling a computer system to schedule a job on one or more available computing resources in a personal datacenter, wherein the instructions, upon execution, cause a processor to perform actions comprising:

determining one or more demands of a job submitted for processing by one or more available computing resources in the personal datacenter;

dividing the job into one or more tasks wherein each task is suitable for performing on one of the available computing resources;

selecting a task of the job for scheduling;

determining a suitable computing resource for performing the selected task by matching the determined demands of the task with capabilities identified for the determined computing resource, wherein determining a suitable device removes from consideration one or more of the available computing resources based upon an anticipated availability of the one or more available computing resources based upon a current time and a historical entry and exit of the device to the personal network and categorizing that device as an unavailable computing resource;

determining an order in which to complete the task; and

storing the determined resource and order as task information in a schedule that can be executed by the available computing resources.