A Hierarchical Cache Coherent Protocol

As the number of processors in distributed-memory multiprocessors grows, efficiently supporting a shared-memory programming model becomes difficult. We have designed the Protocol for Hierarchical Directories (PHD) to allow shared-memory support for systems containing massive numbers of processors. PHD eliminates bandwidth problems by using a scalable network, decreases hot-spots by not relying on a single point to distribute blocks, and uses a scalable amount of space for its directories. PHD provides a shared-memory model by synthesizing a global shared memory from the local memories of processors. PHD supports sequentially consistent read, write, and test- and-set operations. This thesis also introduces a method of describing locality for hierarchical protocols and employs this method in the derivation of an abstract model of the protocol behavior. An embedded model, based on the work of Johnson[ISCA19], describes the protocol behavior when mapped to a k-ary n-cube. The thesis uses these two models to study the average height in the hierarchy that operations reach, the longest path messages travel, the number of messages that operations generate, the inter-transaction issue time, and the protocol overhead for different locality parameters, degrees of multithreading, and machine sizes. We determine that multithreading is only useful for approximately two to four threads; any additional interleaving does not decrease the overall latency. For small machines and high locality applications, this limitation is due mainly to the length of the running threads. For large machines with medium to low locality, this limitation is due mainly to the protocol overhead being too large. Our study using the embedded model shows that in situations where the run length between references to shared memory is at least an order of magnitude longer than the time to process a single state transition in the protocol, applications exhibit good performance. If separate controllers for processing protocol requests are included, the protocol scales to 32k processor machines as long as the application exhibits hierarchical locality: at least 22% of the global references must be able to be satisfied locally; at most 35% of the global references are allowed to reach the top level of the hierarchy.

Mid-Level Vision and Recognition of Non-Rigid Objects

We address mid-level vision for the recognition of non-rigid objects. We align model and image using frame curves - which are object or "figure/ground" skeletons. Frame curves are computed, without discontinuities, using Curved Inertia Frames, a provably global scheme implemented on the Connection Machine, based on: non-cartisean networks; a definition of curved axis of inertia; and a ridge detector. I present evidence against frame alignment in human perception. This suggests: frame curves have a role in figure/ground segregation and in fuzzy boundaries; their outside/near/top/ incoming regions are more salient; and that perception begins by setting a reference frame (prior to early vision), and proceeds by processing convex structures.

A Reinforcement-Learning Approach to Power Management

We describe an adaptive, mid-level approach to the wireless device power management problem. Our approach is based on reinforcement learning, a machine learning framework for autonomous agents. We describe how our framework can be applied to the power management problem in both infrastructure and ad~hoc wireless networks. From this thesis we conclude that mid-level power management policies can outperform low-level policies and are more convenient to implement than high-level policies. We also conclude that power management policies need to adapt to the user and network, and that a mid-level power management framework based on reinforcement learning fulfills these requirements.

Preliminary Observations on Program Instability

This white paper reports emerging findings at the end of Phase I of the Lean Aircraft Initiative in the Policy focus group area. Specifically, it provides details about research on program instability. Its objective is to discuss high-level findings detailing: 1) the relative contribution of different factors to a program’s overall instability; 2) the cost impact of program instability on acquisition programs; and 3) some strategies recommended by program managers for overcoming and/or mitigating the negative effects of program instability on their programs. Because this report comes as this research is underway, this is not meant to be a definitive document on the subject. Rather, is it anticipated that this research may potentially produce a number of reports on program instability-related topics. The government managers of military acquisition programs rated annual budget or production rate changes, changes in requirements, and technical difficulties as the three top contributors, respectively, to program instability. When asked to partition actual variance in their program’s planned cost and schedule to each of these factors, it was found that the combined effects of unplanned budget and requirement changes accounted for 5.2% annual cost growth and 20% total program schedule slip. At a rate of approximately 5% annual cost growth from these factors, it is easy to see that even conservative estimates of the cost benefits to be gained from acquisition reforms and process improvements can quickly be eclipsed by the added cost associated with program instability. Program management practices involving the integration of stakeholders from throughout the value chain into the decision making process were rated the most effective at avoiding program instability. The use of advanced information technologies was rated the most effective at mitigating the negative impact of program instability.

Preliminary Observations on Program Instability

This white paper reports emerging findings at the end of Phase I of the Lean Aircraft Initiative in the Policy focus group area. Specifically, it provides details about research on program instability. Its objective is to discuss high-level findings detailing: 1) the relative contribution of different factors to a program’s overall instability; 2) the cost impact of program instability on acquisition programs; and 3) some strategies recommended by program managers for overcoming and/or mitigating the negative effects of program instability on their programs. Because this report comes as this research is underway, this is not meant to be a definitive document on the subject. Rather, is it anticipated that this research may potentially produce a number of reports on program instability-related topics. The government managers of military acquisition programs rated annual budget or production rate changes, changes in requirements, and technical difficulties as the three top contributors, respectively, to program instability. When asked to partition actual variance in their program’s planned cost and schedule to each of these factors, it was found that the combined effects of unplanned budget and requirement changes accounted for 5.2% annual cost growth and 20% total program schedule slip. At a rate of approximately 5% annual cost growth from these factors, it is easy to see that even conservative estimates of the cost benefits to be gained from acquisition reforms and process improvements can quickly be eclipsed by the added cost associated with program instability. Program management practices involving the integration of stakeholders from throughout the value chain into the decision making process were rated the most effective at avoiding program instability. The use of advanced information technologies was rated the most effective at mitigating the negative impact of program instability.