Software thread integration (STI) helps in hardware to software migration by enabling integration of two independent software threads, which enables execution of the integrated thread in a generic processor. Automation of STI would help in obtaining efficient software versions of many hardware implemented functions. Bit banged communication protocols (BBCP) have been researched for implementation as software threads .Software integration is performed on the different threads of the implementation for obtaining efficient software versions. Though these integrated threads are efficient, these protocols include a message-level thread which is not integrated with any other threads. During integration, cocalls (coroutine calls) are introduced for context switching between integrated threads. The periodic execution requirement of cocalls results in some inefficiency introduced due to idle times introduced in the message level thread between bit level calls. We propose an optimizing algorithm to improve this and distribute the instructions in the message level thread across inter-bit calls to reduce the idle time. Our code optimization algorithm moves code from paths between inter bit calls which are larger (more execution time) to paths between inter bit calls which are smaller (lesser execution time). We adopt data flow analysis techniques similar to those used for partial redundancy elimination and dead code elimination.

LAMMERT, ADAM CRAWFORD. Searching for Better Logic Circuits: Using Artificial Intelligence Techniques to Automate Digital Design. (Under the direction of Dr. Edward Willmore Davis Jr.) Logic circuits are at the core of modern computing. The process of designing circuits which are efficient is thus of critical importance. Usually, logic circuits are designed by human beings who have a specific repertoire of conventional design techniques. These techniques limit the solutions that may be considered during the design process in both form and quality. The limits guide designers through the immense realm of possible circuits, thus making the problem more manageable. Simultaneously, the limits sometimes eliminate from consideration circuits which are optimal in terms of size, depth, etc. By exploring the full range of possible solutions, circuits could be discovered which are superior to the best known human designs. Automated design techniques borrowed from artificial intelligence have allowed exactly that. Specifically, the application of genetic algorithms has allowed the creation of circuits which are substantially superior to the best known human designs. This paper expands on such previous research with a three-fold approach. This approach is comprised of (1) two distinct optimizations for the application of genetic algorithms to design, (2) the formulation and implementation of a systematic search technique to the problem and (3) a comparison of the relative merits of the optimized genetic algorithm and the systematic search technique. It is contended that both genetic algorithms and systematic search can be preferable depending on the situation at hand.

Recent work in the area of narrative generation has sought to develop systems that automatically produce experiences for a user that are understood as stories. Much of this prior work, however, has focused on the structural aspects of narrative rather than the process of narrative comprehension undertaken by readers. Cognitive theories of narrative discourse comprehension define explicit models of a reader's mental state during reading. These cognitive models are created to test hypotheses and explain empirical results about the comprehension processes of readers. They do not often contain sufficient precision for implementation on a computer, and thus, they are not yet suitable for computational generation purposes. This dissertation employs cognitive models of narrative discourse comprehension to define an explicit computational model of a reader's comprehension process during reading, predicting aspects of narrative focus and inferencing with precision. This computational model is employed in a narrative discourse generation system to select content from an event log, creating discourses that satisfy comprehension criteria. The results of three experiments are presented and discussed, exhibiting empirical support for the computational reader model and the results of generation. This dissertation makes a number of contributions that advance the state-of-the-art in narrative discourse generation: a formal model of narrative focus, a formal model of online inferencing in narrative, a method of selecting narrative discourse content to satisfy comprehension criteria, and implementation and evaluation of these models.

Cognitive models have typically dealt with environments that are either artificial or real but too simplistic. This stems from the fact that the process of describing the environment to the cognitive model is a complex vision problem. In order to realize the full potential of cognitive models, it is imperative that they be able to operate in natural domains. We attempt to overcome this limitation by providing a perceptual component to a cognitive model that interacts with more realistic environments. This perceptual component is an image processing substrate that has been customized for two different gaming environments. The substrate formerly worked only for the static environments we associate with conventional graphical user interfaces; the work we describe here extends its functionality to a more general class of interfaces, as represented by the driving game and Mars rover game. A cognitive model built on the ACT-R cognitive architecture has been developed that demonstrates the use of the image processing substrate in performing the driving task.

A router in today's Internet has to satisfy two important properties in order to efficiently provide the Quality of Service (QoS) requested by the users. It should be fair among flows and also have low operational complexity. The packet scheduling techniques that have been proposed earlier do not have both these properties. Schedulers like Weighted Fair Queueing (WFQ) provide good fairness among flows but have high operational complexity. Schedulers like Weighted Round Robin (WRR) are efficient but provide poor fairness among flows. We propose a new packet scheduling technique, Tiered Service Fair Queueing (TSFQ), which is both fair and efficient. We achieve our goal by applying the concept of traffic quantization. A quantized network offers a small set of service levels (tiers), each with its own weight. Each flow is then mapped to one of the service levels so as to guarantee a QoS at least as good as that requested by the flow. We propose different versions of TSFQ, each with its own level of fairness. We present the complexity analysis of the TSFQ scheduler. Finally, we demonstrate through simulations on the TSFQ implementation on $ns-2$, that TSFQ provides good fairness among flows.

The purpose of this research is to show the use of derived data such as materialized views for run time optimization of aggregate queries. In this thesis, we show the trade off between the time taken to design the views Vs the query run time. We have designed a system called Query Performance Enhancement by Tuning (QPET) which implements the idea of designing and using materialized views to answer frequent aggregate queries.

The growing awareness of the network vulnerability draws much attention to security from both the academic community and industrial society. Security is no longer a luxury but an independent and indispensable service to the current Internet. While various security mechanisms such as cryptographic and intrusion detection techniques have been proposed, designed, and even deployed in the field, the newly exposed network vulnerabilities and the emerging network technologies create new security challenges which make the existing security solutions either inefficient or insufficient. My Ph D research focuses on the efficient protection on link state routing and the self-organizing and self-dependent hierarchical public key certificate management in the emerging mobile ad hoc networks. The contributions of this thesis include two parts. In the first part, a cost reduced secure link state routing protocol with the capability of detecting disruptive links is proposed to efficiently protect the routing control messages (e.g., LSA) and trace the faulty intermediate routers; then a confidence extended routing mechanism enhanced with secure virtual links is designed to increase network reachability through selectively including the uncertain routers in packet relaying and further continuously monitoring the behaviors of those selected uncertain routers. A theoretical security analysis and an experimental evaluation are conducted to prove the feasibility and advantages of this new design under various rates of false alarms. In the second part, an approach is presented to discover the optimal PKI certificate path even without help from centralized certificate entities in the non-centralized and infrastructureless mobile ad hoc network and a secured and distributed certificate-chain searching protocol is developed to collect the needed certificates on the fly in the mobile ad hoc network.

Direct manipulation interfaces already employ a weak analogy to the use of physical tools in the real world. Despite certain tradeoffs, a stronger application of tool-using principles can lead to improvements in the design of software interfaces. I outline here some of the theory behind such an approach, and describe the design of systems that follow these principles, with emphasis on a tool-based drawing application called HabilisDraw.

Sensor nodes are low-cost and low-power devices that are prone to node compromises, communication failures and malfunctioning of sensing hardware. As a result, some nodes may report outlying data values, introducing significant deviations in the aggregated sensor readings. This thesis presents a practical resilient outlier detection technique to filter out the influence of the outlying data reported by faulty or compromised nodes. The proposed outlier detection algorithm is based on event localization using minimum mean squared error (MMSE) estimation combined with threshold-based consistency checking to detect outliers. Data aggregation is one of the key techniques commonly used to develop lightweight communication protocols applicable to wireless sensor networks. The proposed approach handles localization of multiple events by grouping the sensor readings into spatially correlated clusters and performing an <I>event-centric</I> detection of outliers. In the entire process of data aggregation, the outlier detection technique fits as a preprocessing stage for reducing the effect of outliers on the aggregated result. Suitable extensions to the basic outlier detection algorithm are proposed to effectively apply the algorithm to both centralized and decentralized sensor network architectures. This thesis further includes studies that test the effectiveness of the proposed approach, including the detection rate, the false positive rate, degree of damage and the resilience to malicious readings introduced by the attackers. The experimental results show that on average the proposed approach detects as high as 80-90% of the outliers while resulting in 5-15% false positive rate when the network consists of 40-45% outliers. The experiments also show that the extent of damage on the aggregated result is below 50% due to the elimination of outliers before aggregation. Finally, the resilient data aggregation process requires modest computational and memory requirements with zero communication overhead in the centralized case and about 20% overhead in the decentralized settings.

Dynamic voltage scaling (DVS) is a promising method to reduce the power consumption of CMOS-based embedded processors. However, pure DVS techniques do not perform well for dynamic systems where the execution times of different jobs vary significantly. A novel DVS scheme with feedback control mechanisms for hard real-time systems is proposed in this work. It produces energy-efficient schedules for both static and dynamic workloads. Task-splitting, slack-passing and preemption-handling schemes are proposed to aggressively reduce the speed of each task. Different feedback control structures are integrated into the DVS algorithm to make it adaptable to workload variations. This scheme relies strictly on operating system support. It is evaluated in simulation as well as on an embedded platform. For given task sets, simulation experiments demonstrate the benefits of this scheme with savings of up to 29\% in energy over previous work. This scheme exhibits up to 24\% additional energy savings over other DVS algorithms on the embedded platform. The feedback-based DVS scheme is further extended to be leakage aware, which considers not only dynamic but also static power consumption caused by leakage current in circuits. A combined DVS, delay and sleeping scheme is proposed for architectures where static power exceeds dynamic power in some cases. DVS is used when dynamic power dominates the total power consumption, while a sleep mode is entered when static power becomes dominant. The extended algorithm, DVSleak, shows 30\% additional energy savings on average over a pure DVS algorithm in the simulation experiment.