This thesis examines the problem of scheduling with incomplete and/or local information in wireless systems. With large numbers of users and limited feedback resources, wireless systems require good scheduling algorithms to attain their performance limits. Classical studies on wireless scheduling investigate in much detail settings where the full state of the system is available when scheduling users. In contrast, this thesis focuses on the case where valuable network state information is lacking at the scheduler, and studies its resulting effect on system performance. The insights gained from the analysis are used to develop efficient wireless scheduling algorithms that operate with limited state information, and that guarantee high throughput and delay performance. The first part of the thesis considers scheduling for stability in a wireless downlink system, where a base station or server schedules transmissions to users, while acquiring channel state information from only subsets of users. It is shown that the system’s throughput region is completely characterized by the marginal channel statistics over observable channel subsets. Effective, queue-length based joint sampling and scheduling algorithms are developed that observe appropriate subsets of channels and schedule users, and the algorithms are shown to be optimal in the sense of throughput. Next, the thesis studies the queue-length performance of wireless scheduling algorithms that use only partial, subset-based channel state information. The chief objective here is to design partial information-based scheduling algorithms that keep the packet queues in the system short, and in this regard, the contributions of this thesis are twofold. First, from the algorithmic perspective, wireless scheduling algorithms using partial channel state information are designed that minimize the likelihood of queue overflow, in a suitable sense, across all partial information scheduling algorithms. The second key contribution is technical, by the development of novel analytical techniques to study the stochastic dynamics of partial state information-based algorithms. These techniques are not only instrumental in showing the optimality results above, but are also of independent interest in understanding the behavior of algorithms which rely on partially sampled system state. The second part of the thesis investigates coordinated inter-cell wireless scheduling across multiple base stations, each possessing only local and partial channel state information for its own users. Coordinated scheduling is necessary to mitigate interference between users in adjacent cells, but information sharing between the base stations is limited by high latencies in the backhauls that interconnect them. A class of distributed scheduling algorithms is developed in which the base stations share only delayed queue length information with each other, and locally acquire partial channel state information, to schedule users. These algorithms are shown to be throughput-optimal, and their average backlog performance in terms of the inter-base station latency is quantified. / text

Current Intel processors implement a variety of power saving features like frequency scaling and idle states. These mechanisms limit the power draw and thereby decrease the thermal dissipation of the processors. However, they also have an impact on the achievable performance. The various mechanisms significantly differ regarding the amount of power savings, the latency of mode changes, and the associated overhead. In this paper, we describe and closely examine the so-called software controlled clock modulation mechanism for different processor generations. We present results that imply that the available documentation is not always correct and describe when this feature can be used to improve energy efficiency. We additionally compare it against the more popular feature of dynamic voltage and frequency scaling and develop a model to decide which feature should be used to optimize inter-process synchronizations on Intel Haswell-EP processors.