High performance grid computing is a key enabler of large scale collaborative computational science. With the promise of exascale computing, high performance grid systems are expected to incur electricity bills that grow super-linearly over time. In order to achieve cost effectiveness in these systems, it is essential for the scheduling algorithms to exploit electricity price variations, both in space and time, that are prevalent in the dynamic electricity price markets. Typically, a job submission in the batch queues used in these systems incurs a variable queue waiting time before the resources necessary for its execution become available. In variably-priced electricity markets, the electricity prices fluctuate over discrete intervals of time. Hence, the electricity prices incurred during a job execution will depend on the start and end time of the job. Our thesis consists of two parts. In the first part, we develop a method to predict the start and end time of a job at each system in the grid. In batch queue systems, similar jobs which arrive during similar system queue and processor states, experience similar queue waiting times. We have developed an adaptive algorithm for the prediction of queue waiting times on a parallel system based on spatial clustering of the history of job submissions at the system. We represent each job as a point in a feature space using the job characteristics, queue state and the state of the compute nodes at the time of job submission. For each incoming job, we use an adaptive distance function, which assigns a real valued distance to each history job submission based on its similarity to the incoming job. Using a spatial clustering algorithm and a simple empirical characterization of the system states, we identify an appropriate prediction model for the job from among standard deviation minimization method, ridge regression and k-weighted average. We have evaluated our adaptive prediction framework using historical production workload traces of many supercomputer systems with varying system and job characteristics, including two Top500 systems. Across workloads, our predictions result in up to 22% reduction in the average absolute error and up to 56% reduction in the percentage prediction errors over existing techniques. To predict the execution time of a job, we use a simple model based on the estimate of job runtime provided by the user at the time of job submission. In the second part of the thesis, we have developed a metascheduling algorithm that schedules jobs to the individual batch systems of a grid, to reduce both the electricity prices for the systems and response times for the users. We formulate the metascheduling problem as a Minimum Cost Maximum Flow problem and leverage execution period and electricity price predictions to accurately estimate the cost of job execution at a system. The network simplex algorithm is used to minimize the response time and electricity cost of job execution using an appropriate flow network. Using trace based simulation with real and synthetic workload traces, and real electricity price data sets, we demonstrate our approach on two currently operational grids, XSEDE and NorduGrid. Our experimental setup collectively constitute more than 433K processors spread across 58 compute systems in 17 geographically distributed locations. Experiments show that our approach simultaneously optimizes the total electricity cost and the average response time of the grid, without being unfair to users of the local batch systems. Considering that currently operational HPC systems budget millions of dollars for annual operational costs, our approach which can save $167K in annual electricity bills, compared to a baseline strategy, for one of the grids in our test suite with over 76000 cores, is very relevant for reducing grid operational costs in the coming years.

[pt] Nesta de tese de doutorado é proposta uma metodologia alternativa para obter estratégias ótimas de oferta sob incerteza que maximizam o lucro de um agente em mercados dotados de um leilão de preço uniforme e envelope fechado com multiplos produtos divisíveis. A estratégia ótima de um agente price maker depende amplamente da informação conhecida dos agentes rivais. Reconhecendo que a oferta dos agentes rivais pode desviar do equilíbrio de mercado e é de difícil caracterização probabilística, nós propomos um modelo de otimização robusta dois estágios com restrições de equilíbrio para obter estratégias de oferta ótimas avessas a risco. O modelo proposto é um modelo de otimização de três níveis passível de ser reescrito como uma instância particular de um programa binível com restrições de equilíbrio. Um conjunto de procedimentos é proposto a fim de construir uma formulação equivalente de de nível único adequado para aplicação de algoritmos de Geração de Coluna e Restrição (GCC). Diferentemente de trabalhos publicados anteriormente em modelos de otimização dois estágios, nossa metodologia de solução não aplica o método de GCC para iterativamente identificar os cenários mais violados dos fatores de incerteza, variáveis que são identificadas através de variáveis contínuas. Na metodologia de solução proposta, o algoritmo GCC é aplicado para identificar um pequeno subconjunto de condições de otimalidade para o modelo de terceiro nível capaz de representar as restrições de equilíbrio do leilão na solução ótima do problema master (problema de oferta). Um estudo de caso numérico baseado em mercados de energia de curto prazo é apresentado para ilustrar a aplicabilidade do modelo robusto proposto. Resultados indicam que mesmo em um caso em que é observada uma imprecisão de 1 porcento na oferta de equilíbrio de Nash dos agentes rivais, a solução robusta provê uma redução significativa de risco em uma análise fora da amostra. / [en] We propose an alternative methodology to devise profit-maximizing strategic bids under uncertainty in markets endowed with a sealed-bid uniformprice auction with multiple divisible products. The optimal strategic bid of a price maker agent largely depends on the knowledge (information) of the rivals bidding strategy. By recognizing that the bid of rival competitors may deviate from the equilibrium and are of difficult probabilistic characterization, we proposed a two-stage robust optimization model with equilibrium constraints to devise an risk-averse strategic bid in the auction. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures are proposed to construct a single-level-equivalent formulation suitable for column and constraint generation (CCG) algorithm. Differently from previously reported works on two-stage robust optimization, our solution methodology does not employ the CCG algorithm to iteratively identify violated scenarios for the uncertain factors, which in this thesis are obtained through continuous variables. In the proposed solution methodology, the CCG is applied to identify a small subset of optimality conditions for the third-level model capable of representing the auction equilibrium constraints at the optimum solution of the master (bidding) problem. A numerical case study based on short-term electricity markets is presented to illustrate the applicability of the proposed robust model. Results show that even for the case where an impression of 1 percent on the rivals offer at the Nash equilibrium is observed, the robust solution provides a non-negligible risk reduction in out-of-sample analysis.