Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Market-Based Resource Allocation using Price Prediction in a high performance computing Grid for scientific applications
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. KTH, School of Information and Communication Technology (ICT), Computer and Systems Sciences, DSV.
Hewlett-Packard Laboratories, Information Dynamics Laboratory, Palo Alto.
KTH, School of Biotechnology (BIO), Gene Technology.
KTH, School of Biotechnology (BIO), Gene Technology.ORCID iD: 0000-0003-0996-1644
2006 (English)In: Proceedings of the IEEE International Symposium on High Performance Distributed Computing 2006, 2006, Vol. 15th IEEE International Symposium, 132-143 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present the implementation and analysis of a market-based resource allocation system for computational Grids. Although Grids provide a way to share resources and take advantage of statistical multiplexing, a variety of challenges remain. One is the economically efficient allocation of resources to users from disparate organizations who have their own and sometimes conflicting requirements for both the quantity and quality of services. Another is secure and scalable authorization despite rapidly changing allocations.

Our solution to both of these challenges is to use a market-based resource allocation system. This system allows users to express diverse quantity- and quality-of-service requirements, yet prevents them from denying service to other users. It does this by providing tools to the user to predict and tradeoff risk and expected return in the computational market. In addition, the system enables secure and scalable authorization by using signed money-transfer tokens instead of identity-based authorization. This removes the overhead of maintaining and updating access control lists, while restricting usage based on the amount of money transferred We examine the performance of the system by running a bioinformatics application on a fully operational implementation of an integrated Grid market.

Place, publisher, year, edition, pages
2006. Vol. 15th IEEE International Symposium, 132-143 p.
Keyword [en]
Computational methods, Marketing, Multiplexing, Quality of service, Resource allocation, Statistical methods, Computational market, Computing grid, Market based resource allocation system, Quantity of service
National Category
Industrial Biotechnology Information Science
Identifiers
URN: urn:nbn:se:kth:diva-7799DOI: 10.1109/HPDC.2006.1652144ISI: 000239086500011Scopus ID: 2-s2.0-33845897137OAI: oai:DiVA.org:kth-7799DiVA: diva2:12928
Conference
The IEEE International Symposium on High Performance Distributed Computing 2006
Note
QC 20100622Available from: 2007-12-10 Created: 2007-12-10 Last updated: 2010-11-16Bibliographically approved
In thesis
1. Grid and High-Performance Computing for Applied Bioinformatics
Open this publication in new window or tab >>Grid and High-Performance Computing for Applied Bioinformatics
2007 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

The beginning of the twenty-first century has been characterized by an explosion of biological information. The avalanche of data grows daily and arises as a consequence of advances in the fields of molecular biology and genomics and proteomics. The challenge for nowadays biologist lies in the de-codification of this huge and complex data, in order to achieve a better understanding of how our genes shape who we are, how our genome evolved, and how we function.

Without the annotation and data mining, the information provided by for example high throughput genomic sequencing projects is not very useful. Bioinformatics is the application of computer science and technology to the management and analysis of biological data, in an effort to address biological questions. The work presented in this thesis has focused on the use of Grid and High Performance Computing for solving computationally expensive bioinformatics tasks, where, due to the very large amount of available data and the complexity of the tasks, new solutions are required for efficient data analysis and interpretation.

Three major research topics are addressed; First, the use of grids for distributing the execution of sequence based proteomic analysis, its application in optimal epitope selection and in a proteome-wide effort to map the linear epitopes in the human proteome. Second, the application of grid technology in genetic association studies, which enabled the analysis of thousand of simulated genotypes, and finally the development and application of a economic based model for grid-job scheduling and resource administration.

The applications of the grid based technology developed in the present investigation, results in successfully tagging and linking chromosomes regions in Alzheimer disease, proteome-wide mapping of the linear epitopes, and the development of a Market-Based Resource Allocation in Grid for Scientific Applications.

Place, publisher, year, edition, pages
Stockholm: KTH, 2007
Series
Trita-BIO-Report, ISSN 1654-2312 ; 2007:9
Keyword
Grid computing, bioinformatics, genomics, proteomics
National Category
Bioinformatics (Computational Biology)
Identifiers
urn:nbn:se:kth:diva-4573 (URN)978-91-7178-782-8 (ISBN)
Public defence
2007-12-21, FD5, AlbaNova, oslagstullsbacken 21, Stockholm, 10:00
Opponent
Supervisors
Note
QC 20100622Available from: 2007-12-10 Created: 2007-12-10 Last updated: 2012-03-20Bibliographically approved
2. Statistical Methods for Computational Markets: Proportional Share Market Prediction and Admission Control
Open this publication in new window or tab >>Statistical Methods for Computational Markets: Proportional Share Market Prediction and Admission Control
2008 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

We design, implement and evaluate statistical methods for managing uncertainty when consuming and provisioning resources in a federated computational market. To enable efficient allocation of resources in this environment, providers need to know consumers' risk preferences, and the expected future demand. The guarantee levels to offer thus depend on techniques to forecast future usage and to accurately capture and model uncertainties. Our main contribution in this thesis is threefold; first, we evaluate a set of techniques to forecast demand in computational markets; second, we design a scalable method which captures a succinct summary of usage statistics and allows consumers to express risk preferences; and finally we propose a method for providers to set resource prices and determine guarantee levels to offer. The methods employed are based on fundamental concepts in probability theory, and are thus easy to implement, as well as to analyze and evaluate. The key component of our solution is a predictor that dynamically constructs approximations of the price probability density and quantile functions for arbitrary resources in a computational market. Because highly fluctuating and skewed demand is common in these markets, it is difficult to accurately and automatically construct representations of arbitrary demand distributions. We discovered that a technique based on the Chebyshev inequality and empirical prediction bounds, which estimates worst case bounds on deviations from the mean given a variance, provided the most reliable forecasts for a set of representative high performance and shared cluster workload traces. We further show how these forecasts can help the consumers determine how much to spend given a risk preference and how providers can offer admission control services with different guarantee levels given a recent history of resource prices.

Place, publisher, year, edition, pages
Stockholm: KTH, 2008. xii, 75 p.
Series
Report series / DSV, ISSN 1101-8526 ; 08-006
Keyword
Distributed Systems, Grid Computing, Performance Analysis, Workload Modeling, Middleware, Quality of Service, Prediction, Admission Control
National Category
Information Science
Identifiers
urn:nbn:se:kth:diva-4738 (URN)978-91-7178-924-2 (ISBN)
Public defence
2008-05-26, Hall C, KTH-Forum, Isafjordsgatan 39, Stockholm, 13:00
Opponent
Supervisors
Note
QC 20100909Available from: 2008-05-09 Created: 2008-05-09 Last updated: 2010-09-09Bibliographically approved
3. Managing Service Levels in Grid Computing Systems: Quota Policy and Computational Market Approaches
Open this publication in new window or tab >>Managing Service Levels in Grid Computing Systems: Quota Policy and Computational Market Approaches
2007 (English)Licentiate thesis, comprehensive summary (Other scientific)
Abstract [en]

We study techniques to enforce and provision differentiated service levels in Computational Grid systems. The Grid offers simplified provisioning of peak-capacity for applications with computational requirements beyond local machines and clusters, by sharing resources across organizational boundaries. Current systems have focussed on access control, i.e., managing who is allowed to run applications on remote sites. Very little work has been done on providing differentiated service levels for those applications that are admitted. This leads to a number of problems when scheduling jobs in a fair and efficient way. For example, users with a large number of long-running jobs could starve out others, both intentionally and non-intentionally. We investigate the requirements of High Performance Computing (HPC) applications that run in academic Grid systems, and propose two models of service-level management. Our first model is based on global real-time quota enforcement, where projects are granted resource quota, such as CPU hours, across the Grid by a centralized allocation authority. We implement the SweGrid Accounting System to enforce quota allocated by the Swedish National Allocations Committee in the SweGrid production Grid, which connects six Swedish HPC centers. A flexible authorization policy framework allows provisioning and enforcement of two different service levels across the SweGrid clusters; high-priority and low-priority jobs. As a solution to more fine-grained control over service levels we propose and implement a Grid Market system, using a market-based resource allocator called Tycoon. The conclusion of our research is that although the Grid accounting solution offers better service level enforcement support than state-of-the-art production Grid systems, it turned out to be complex to set the resource price and other policies manually, while ensuring fairness and efficiency of the system. Our Grid Market on the other hand sets the price according to the dynamic demand, and it is further incentive compatible, in that the overall system state remains healthy even in the presence of strategic users.

Place, publisher, year, edition, pages
Stockholm: KTH, 2007. v, 35 p.
Series
Trita-CSC-A, ISSN 1653-5723 ; 2007:6
Keyword
Grid Market, Computational Grid, Service Level Management, QoS, HPC, Grid Middleware
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-4346 (URN)978-91-7178-658-6 (ISBN)
Presentation
2007-05-14, Rum 304, KTH, Teknikringen 14, Stockholm, 10:00
Supervisors
Note
QC 20101116Available from: 2007-05-02 Created: 2007-05-02 Last updated: 2010-11-16Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Sandholm, ThomasAndrade, JorgeOdeberg, Jacob
By organisation
Centre for High Performance Computing, PDCComputer and Systems Sciences, DSVGene Technology
Industrial BiotechnologyInformation Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 98 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf