Scheduling algorithms based on game theory makes better use of computational resources

June 18, 2014
Computer science: Right on schedule
A new scheme developed for the efficient allocation of computational resources relies on three game-theory-based scheduling algorithms that help minimize execution time, reduce cost and limit storage requirements. Credit: agsandrew/istock/thinkstock

Grid computing is a powerful form of distributed computing wherein a network of loosely coupled and geographically separated computers, typically of different computational powers, work together to perform data-intensive calculations. The technology uses numerical simulations to help investigate a variety of challenging scientific problems, including the subatomic world revealed by particle accelerators like the Large Hadron Collider.

The current trend in the industry is to build grid-computing systems that can run not just one but multiple large-scale, . While most systems can guarantee good performance, this is usually accompanied by significant cost and large storage requirements. To optimize the cost–performance relationship of large-scale grid-computing systems, scientists must overcome several issues—one of which is the efficient allocation of computational resources, known as scheduling.

Rubing Duan and Xiaorong Li at the A*STAR Institute of High Performance Computing in Singapore and co-workers have now developed a scheme to address the scheduling problem in two large-scale applications: the ASTRO program from the field of cosmology, which simulates the movements and interactions of galaxy clusters, and the WIEK2k program from the field of theoretical chemistry, which calculates the electronic structure of solids1. The researchers' new scheme relies on three game-theory-based scheduling algorithms: one to minimize the execution time; one to reduce the economic cost; and one to limit the storage requirements.

The researchers performed calculations wherein they stopped the competition for resources when the iteration reached the upper limit of optimization. They compared their simulation results with those from related algorithms—namely, Minimum Execution Time, Minimum Completion Time, Opportunistic Load Balancing, Max-min, Min-min and Sufferage. The new approach showed improvements in terms of speed, cost, scheduling results and fairness. Furthermore, the researchers found that the execution time improved as the scale of the experiment increased. In one case, their approach delivered results within 0.3 seconds while other algorithms needed several hours.

Nonetheless, the researchers note that their algorithms may not be suited for applications that are highly heterogeneous.

Prior to this study, only a handful of work had considered the optimization of multiple metrics. However, Duan, Li and colleagues were able to present a model approach to reducing the execution time, economic cost and storage requirements in grid-computing systems, especially when used in large-scale applications.

"Our game-theory-based scheduling algorithms possess great potential for large-scale applications," says Duan. "We are looking into how the algorithms adapt to other metrics, such as memory, security, resource availability, network bandwidth and multiple virtual organizations."

Explore further: Parallel in time algorithms enable simulation of long-lasting chemical processes

More information: Duan, R., Prodan, R. & Li, X. "A sequential cooperative game theoretic approach to scheduling multiple large-scale applications in grids." Future Generation Computer Systems 30, 27–43 (2014).

Related Stories

Better chemistry through parallel in time algorithms

March 17, 2014

Molecular dynamics simulations often take too long to be practical for simulating chemical processes that occur on long timescales. Scientists DOE's Pacific Northwest National Laboratory, the University of Chicago, and the ...

Parallel programming may not be so daunting

March 24, 2014

Computer chips have stopped getting faster: The regular performance improvements we've come to expect are now the result of chipmakers' adding more cores, or processing units, to their chips, rather than increasing their ...

The road to quantum computing

May 15, 2014

Anticipating the advent of the quantum computer, related mathematical methods already provide insight into conventional computer science.

Efficient processing of big data on a daily routine basis

June 10, 2014

Computer systems today can be found in nearly all areas of life, from smartphones to smart cars to self-organized production facilities. These computer systems supply rapidly growing data volumes. Computer science now faces ...

Recommended for you

The ethics of robot love

November 25, 2015

There was to have been a conference in Malaysia last week called Love and Sex with Robots but it was cancelled. Malaysian police branded it "illegal" and "ridiculous". "There is nothing scientific about sex with robots," ...

Glider pilots aim for the stratosphere

November 20, 2015

Talk about serendipity. Einar Enevoldson was strolling past a scientist's office in 1991 when he noticed a freshly printed image tacked to the wall. He was thunderstruck; it showed faint particles in the sky that proved something ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.