Obviousness

Obviousness Analysis under 35 U.S.C. § 103 for US Patent 7257582

A patent claim is considered obvious under 35 U.S.C. § 103 if "the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains." The motivation to combine references can come from various sources, including the nature of the problem to be solved, the design needs or market pressures, or the known methods for combining elements found in the prior art.

US Patent 7257582 aims to enable the decomposition of linear processes into equivalent parallel processes that can efficiently use any number of potentially heterogeneous computers, taking available capacity into account while optimizing execution, and to improve processing efficiency generally. The core of independent claim 1 describes:
(a) automatically determining file allocation and logically subdividing records of an input file into a plurality of partitions;
(b) distributing descriptions of all partitions to each of a plurality of subtask processors;
(c) simultaneously executing subtasks on respective partitions in at least some processors, producing subtask output;
(d) repeating step (c) in at least some subtask processors with another unprocessed partition on a first-come/first-served basis; and
(e) generating at least one output combining all subtask outputs.

Below are combinations of prior art references that would render the claims of US7257582 obvious to a person having ordinary skill in the art (PHOSITA).

Combination 1: US6275867B1 in view of US5357632A and US5926833A

This combination addresses independent claim 1 and several dependent claims by combining the concepts of operation partitioning, dynamic task allocation, and heterogeneous system data access.

• US6275867B1 (Operation-partitioned off-loading of operations in a distributed environment): This patent teaches the fundamental concept of partitioning operations and off-loading them to processors in a distributed environment. This directly addresses elements (a) "logically subdividing records... into a plurality of partitions" and (b) "distributing descriptions of all of said partitions to each of a plurality of subtask processors" for processing in a distributed manner. It also covers (c) "simultaneously executing at least a respective one of the subtasks... in each of at least some of said processors on a respective one of the partitions."
• US5357632A (Dynamic task allocation in a multi-processor system): This reference describes a multiprocessor system with dynamic task allocation, where tasks are assigned to processors based on system load to efficiently utilize resources. This explicitly provides the mechanism for element (d) "repeating step (c)... with another unprocessed partition on a first-come/first-served basis," as dynamic allocation to balance load inherently involves subtasks taking available work. The patent also aligns with the objective of US7257582 to optimize execution by taking available capacity into account.
• US5926833A (Direct data access to a shared data storage subsystem by heterogeneous computing systems): This patent teaches a method and system enabling heterogeneous computing systems to directly access shared data storage. This foundational technology is crucial for implementing the system described in US7257582, where input and output files are shared by potentially heterogeneous systems, as stated in the patent's background and detailed description. It thus enables the scenario where a "plurality of subtask processors" are "mutually heterogeneous" (as in dependent claims 2 and 12).

Motivation to Combine:
A PHOSITA, aiming to build a more efficient and flexible distributed processing system, would be motivated to combine these references. US6275867B1 provides the initial framework for distributing parts of a task across multiple processors. However, for optimal performance and load balancing, a static distribution is often suboptimal. Therefore, a PHOSITA would naturally look to integrate dynamic task allocation mechanisms, such as those taught in US5357632A, to ensure that processors pick up new tasks (partitions) on a first-come/first-served basis, proportional to their capacity and current load. Furthermore, recognizing the prevalence of heterogeneous computing environments and shared storage, it would be obvious to incorporate the teachings of US5926833A to allow these distributed, dynamically assigned tasks to seamlessly access and process data from a shared storage subsystem, regardless of the underlying hardware heterogeneity. This combination directly leads to the method of independent claim 1, allowing for efficient load balancing with shared data in heterogeneous environments.

Combination 2: US6480876B2 in view of JP3640580B2 and US5926833A

This combination particularly addresses the application of load balancing to specific computer-executable processes, such as sorting (claim 8), while encompassing the general method of claim 1.

• US6480876B2 (System for integrating task and data parallelism in dynamic applications): This patent describes a system that integrates both task and data parallelism. This directly encompasses elements (a) "logically subdividing records... into a plurality of partitions," (b) "distributing descriptions of all of said partitions to each of a plurality of subtask processors," (c) "simultaneously executing at least a respective one of the subtasks," and (d) "thereafter repeating step (c)... on a first-come/first-served basis" (as dynamic applications inherently support adaptive task distribution).
• JP3640580B2 (Sort / merge processor): This patent specifically describes a sort/merge processor. Sorting is explicitly identified as a key application in US7257582. A sort/merge process inherently involves partitioning input data, sorting these partitions independently (subtasks), and then merging the sorted sub-outputs to produce a final sorted output. This directly teaches element (e) "generating at least one output combining all of the subtask outputs," particularly in the context of a sort process, thus making claim 8 obvious.
• US5926833A (Direct data access to a shared data storage subsystem by heterogeneous computing systems): As in Combination 1, this patent enables the shared data access between heterogeneous computing systems, which is a prerequisite for the overall system functionality described in US7257582.

Motivation to Combine:
A PHOSITA working on improving the performance of common, data-intensive applications like sorting (a prime example given in US7257582) would find US6480876B2's framework for integrating task and data parallelism highly relevant. To implement an efficient parallel sort, they would naturally look to specific solutions for sorting, such as the "sort/merge processor" described in JP3640580B2, which details the necessary partitioning, distributed sorting, and final merging steps. Recognizing that such large-scale data processing often occurs in environments with shared storage and potentially diverse hardware, the PHOSITA would integrate the teachings of US5926833A to ensure all processors can efficiently access the common input and output files across heterogeneous systems. This combination results in a distributed, load-balanced sorting method as described in claim 1 and specifically claim 8 of US7257582.

Combination 3: US5819021A in view of US5357632A and US5926833A

This combination further emphasizes the partitioning aspect and dynamic allocation for efficiency.

• US5819021A (Overpartitioning system and method for increasing checkpoints in component-based parallel applications): This patent teaches "overpartitioning" in parallel applications, where tasks are subdivided into more partitions than available processors. This directly addresses element (a) "logically subdividing records... into a plurality of partitions" and inherently implies (b) "distributing descriptions" and (c) "simultaneously executing" subtasks. Overpartitioning creates a pool of tasks, which naturally lends itself to dynamic allocation.
• US5357632A (Dynamic task allocation in a multi-processor system): As discussed, this reference provides the mechanism for dynamic task allocation based on system load, directly addressing element (d) "repeating step (c)... on a first-come/first-served basis."
• US5926833A (Direct data access to a shared data storage subsystem by heterogeneous computing systems): This patent provides the underlying shared data access for heterogeneous systems, essential for the practical implementation of the invention.

Motivation to Combine:
A PHOSITA designing a parallel application system, such as one employing overpartitioning for fault tolerance or granularity management as in US5819021A, would recognize that simply distributing these many partitions statically might lead to imbalances. To ensure efficient utilization of all available processing resources, especially when processor capacities or loads vary, it would be obvious to incorporate a dynamic task allocation scheme, such as that described in US5357632A, allowing processors to pull available partitions on a first-come/first-served basis. Furthermore, to enable this system to operate in realistic, distributed computing environments where data resides in shared storage accessible by heterogeneous machines, the PHOSITA would integrate the teachings of US5926833A. This combination would result in a robust, load-balanced, parallel processing system that addresses all elements of claim 1.

These combinations demonstrate that the core methodology of US7257582, including logical subdivision, distributed processing, first-come/first-served allocation for load balancing, and output generation, would have been obvious to a PHOSITA given the collective teachings of the cited prior art. The specific applications (sort, database query, etc.) listed in dependent claims (8-11) are likewise rendered obvious by references such as JP3640580B2 and US5835755A, or are simply well-known applications for parallel processing techniques.