51 |
Statistical Delay Bounds Oriented Packet Scheduling Algorithms in High Speed NetworksZhu, Kai 21 September 2000 (has links)
<p>Zhu, Kai. <b>Statistical Delay Bounds Oriented Packet Scheduling Algorithms inHigh Speed Networks.</b> (Under the direction of Prof. Yannis Viniotis)<P>We first present a strategic analysis of end-to-end delay bounds and identify heuristics for scheduler design, then propose three new schedulers that are targeted at statistical delay bounds: Deadline-curve basedEarliest Deadline First (DC-EDF), Adaptive Quasi-Earliest Deadline First (AQE)and General Dynamic Guaranteed Rate Queueing (GDGRQ).<P>Under DC-EDF, local deadlines are assigned as strict time-shifted versions ofsource packet arrival times. This is quite different from the well-known RC-EDF(Rate-controlled EDF), which deploys traffic shaping at each switching node. Weshow that even without traffic shapers, DC-EDF provides not only end-to-enddelay bounds, but also a schedulable region as large as that of RC-EDF. DC-EDFis self-adaptive in local delay bound assignments. This property makes DC-EDFsuitable as the scheduler at intermediate switching nodes along a flow's route.<P>AQE is an enhancement of EDF with intelligence of adaptive scheduling. Under AQEpercentile delay bounds are the delay QoS metric. AQE behaves like EDF whenbandwidth is sufficient. When bandwidth becomes deficient, however, AQE onlyschedules a subset of flows which currently have relatively worse performance;other flows are completely blocked and will be unblocked only when bandwidthbecomes sufficient again. Essentially, AQE enforces shaping on packet delaydistributions. AQE is most suited for scheduling at the last switching nodealong a flow's route. The combination of DC-EDF and AQE provides a good solutiontowards statistical end-to-end delay bounds.<P>GDGQR is designed for networks with fixed packet sizes. It is a subclass of thewell-known Guaranteed Rate (GR) schedulers, thus can guarantee minimum rates toflows. The GR property of GDGRQ is retained through a sophisticated datastructure called cell transmission table. The unique feature of GDGRQ is that itallows controllable adaptive strategy of excess bandwidth distribution, which isrealized by short-term rate adjustment according to queue measurement. GDGRQ isa framework for designing schedulers that can both provide (possibly large)deterministic delay bounds and allow statistical delay bounds.<P>
|
52 |
An Implementation of Differentiated Services In A Linux EnvironmentNarasimhan, Kesava Prasad 06 December 2000 (has links)
<p>Narasimhan, Kesava Prasad. An Implementation of Differentiated Services In A Linux Environment. (Under the direction of Dr. Yannis Viniotis and Dr. Mladen Vouk.)The purpose of this project has been to implement a differentiated services (diffserv) router in software in a Linux environment. The objective is to enable the construction of a test-bed of such diffserv routers. One of the design goals is to make the software as modular as possible. This permits the various modules of the diffserv router to be configured easily. In addition, a very user-friendly script file interface was designed to configure the diffserv modules. Consideration was also given to the fact that in future, this code is expected to be integrated with a policy server. In this project, the emphasis was on functionality and not on performance. Hence, not much effort was taken towards optimizing the performance of the diffserv router. <P>
|
53 |
COMPUTER AIDED TOOLSFORSEAMLESS HIGH DENSITY INTERCONNECTSVarma, Ambrish Kant 12 April 2001 (has links)
<p><B>Varma, Ambrish Kant. Computer - Aided Tools for Seamless High DensityInterconnects. (Under the direction of Paul D. Franzon)</B><BR>This thesis presents the tool-set designed to demonstrate the possibility of using theCadence tools to design, verify and extract circuitry on the substrate along with theon-chip design. This circuitry could be an inter-chip connection that connects twodifferent chips or an intra-chip connection where a long interconnect is taken off fromthe active area of the chip to the substrate and back on to the same chip.<BR>To be able to do this task, the work for this project is broadly classified into fourdifferent categories. These are writing<BR> The technology file and the display.drf file The Design Rule Check deck The Layout Verses Schematic deckAfter having completed the above-mentioned tasks, the tool-set was also tested andimplemented on a circuit.<P>
|
54 |
Compiler-Driven Value Speculation SchedulingFu, Chao-ying 10 May 2001 (has links)
<p>Modern microprocessors utilize several techniques for extracting instruction-level parallelism (ILP) to improve the performance. Current techniques employed in the microprocessor include register renaming to eliminate register anti- and output (false) dependences, branch prediction to overcome control dependences, and data disambiguation to resolve memory dependences. Techniques for value prediction and value speculation have been proposed to break register flow (true) dependences among operations, so that dependent operations can be speculatively executed without waiting for producer operations to finish. This thesis presents a new combined hardware and compiler synergy, value speculation scheduling (VSS), to exploit the predictability of operations to improve the performance of microprocessors. The VSS scheme can be applied to dynamically-scheduled machines and statically-scheduled machines. To improve the techniques for value speculation, a value speculation model is proposed as solving an optimal edge selection problem in a data dependence graph. Based on three properties observed from the optimal edge selection problem, an efficient algorithm is designed and serves as a new compilation phase of benefit analysis to know which dependences should be broken to obtain maximal benefits from value speculation. A pure software technique is also proposed, so that existing microprocessors can employ software-only value speculation scheduling (SVSS) without adding new value prediction hardware and modifying processor pipelines. Hardware-based value profiling is investigated to collect highly predictable operations at run-time for reducing the overhead of program profiling and eliminating the need of profile training inputs.<P>
|
55 |
Algorithm Partitioning and Scheduling for Adaptive ComputersDoss, Christopher 27 June 2001 (has links)
<p>Adaptive, or reconfigurable, computing has emerged as a viable computing alternative for computationally intense applications. (We use the terms adaptive and reconfigurable interchangeably). Here, an adaptive computer is a computing system that contains a general purpose processor attached to a programmable logic device such as a field programmable gate array (FPGA). These computing systems combine the flexibility of general purpose processors with the speed of application specific processors. The computer system designer can cater the hardware to a specific application by modifying the configuration of the FPGAs. The designer can reconfigure the FPGAs at some future time for other applications since the FPGAs do not have a fixed structure.Several reconfigurable computers have been implemented to demonstrate the viability of reconfigurable processors.Applications mapped to these processors include pattern recognition in high-energy physics, statistical physics and genetic optimization algorithms. In many cases, the reconfigurable computing implementation provided thehighest performance, in terms of execution speed, published (at the respective time).To achieve such performance, the application must effectively utilize the available resources. This presents a challenge for software designers, who are generally used to mapping applications onto fixed computing systems.Generally, the designers examine the available hardware resources and modify their application accordingly. With reconfigurable computers, the available resources can be generated when needed. While it may seem thatthis flexibility would ease the mapping process, it actually introduces new problems, such as what components should be allocated, and how many of each component should be used to generate the best performance. With conventionalhardware components, these questions were not an issue.In addition, software engineers are generally not adept at hardware design.In this dissertation, we present a design methodology for systematically implementing computationally intense applications on reconfigurable computing systems. This methodology is based on concepts from compiler theory to ease automation.In addition to the design methodology, we present, a toolthat implements a significant portion of the design methodology. RAS can be considered as a module generation tool for assisting the design process. Given a flow graph representing a loop nest, RAS allocates a set of resources, and schedules the nodes of the graph to the resources. RAS also generates an estimate of the amount of time it would take if the design implemented according to the schedule.This dissertation also presents results of designs produced by RAS. Multiple tests were performed using three computationally intense algorithms. RAS mapped the algorithms to five configurations representingdifferent sets of resource constraints. Two of the configurations were based on actual systems used in the research development, while the remainingthree were hypothetical systems based on other components available in the market. Experimental results from RASindicate that a significant amount of speedup is attainable using the allocated resources with the given schedule.<P>
|
56 |
INTRUSION TOLERANT SYSTEMS CHARACTERIZATION AND ACCEPTANCE MONITOR DESIGNWang, Rong 27 June 2001 (has links)
<p> Intrusion detection research has been so far mostly concentrated on techniques that effectively identify the malicious behaviors. No assurance can be assumed once a system is compromised. Intrusion tolerance, on the other hand, focuses on providing the desired services even when some components have been compromised. A DARPA-funded research project named SITAR (A Scalable Intrusion-Tolerant Architecture for Distributed Services) investigates the intrusion tolerance further in distributed systems to provide reliable services. Two specific challenges are addressed in this project: the first is how to take advantage of fault tolerant techniques in intrusion tolerant systems; the second is how to deal with possible attacks and compromised components so as to continue providing the service. This thesis represents part of the on-going development of the SITAR project. First, a state transition model is developed to describe the dynamic behavior of an intrusion tolerant system. Second, the Acceptance Monitor is designed to detect the system compromises from the request-response stream. Third, various kinds of vulnerabilities on Web-based COTS services are investigated and one specific design of the Acceptance Monitor is proposed and implemented for a Web-based COTS service to show the effectiveness of the proposed approach. We hope by utilizing the fault tolerance methodologies on the intrusion tolerance system we can solve the problem of providing reliable distributed services that are invulnerable to both known and unknown intrusions. <P>
|
57 |
A Methodology for Study of Network Processing ArchitecturesSuryanarayanan, Deepak 20 July 2001 (has links)
<p>A new class of processors has recently emerged that encompasses programmable ASICs and microprocessors that can implement adaptive network services. This class of devices is collectively known as Network Processors (NP). NPs leverage the flexibility of software solutions with the high performance of custom hardware. With the development of such sophisticated hardware, there is a need for a holistic methodology that can facilitate study of Network Processors and their performance with different networking applications and traffic conditions. This thesis describes the development of Component Network Simulator (ComNetSim) that is based on such a tech-nique. The simulator demonstrates the implementation of Diffserv applications on a Network Processor architecture and the performance of the system under different network traffic conditions.<P>
|
58 |
Architectural and Compiler Issues for Tolerating Latencies in Horizontal ArchitecturesOzer, Emre 04 September 2001 (has links)
<p>This dissertation presents a new architecture model named Weld for horizontal architectures such as VLIW and EPIC. Weld integrates speculative multithreading support into a VLIW/EPIC processor to hide run-time latency effects that cannot be determined by the compiler. Also, it proposes a hardware technique called operation welding that merges operations from different threads to utilize the hardware resources more efficiently. Hardware contexts such as program counters and the fetch units are duplicated to support multithreading. Also, a dual-thread Weld architecture is isolated and analyzed for cost/performance purposes within the general Weld architecture. The dual-thread Weld model supports one main thread and one speculative thread running simultaneously in a VLIW/EPIC processor with a register file and a fetch unit per thread. The cost/performance impact of the dual-thread Weld model, which includes analysis of migrating the disambiguation hardware to the compiler and the sensitivity analysis to the variation of branch misprediction and second-level cache miss penalties, is examined further. <P>
|
59 |
A Low-Power, High Performance MEMS-based Switch FabricDuewer, Bruce Eliot 17 October 2001 (has links)
<p>DUEWER, BRUCE ELIOT. A Low-Power, High Performance MEMS-based Switch Fabric. (Under the direction of Paul D. Franzon.)An approach with the potential for building large low power high performance crossbar networks is presented. Thin film polysilicon MEMS devices are developed to provide crosspoints. These devices are vertically moving plates that serve as variable capacitors. Addressing of large arrays using 2n rather than n-squared lines despite no active circuitry on the MEMS chips is facilitated by bistable device operation. Derivations of equations for bistable device operation are presented. Low power operation is possible as the devices are electrostatically controlled and are stationary except during reconfiguration. Early devices are fabricated using the MUMPS process. The bistability and array addressability properties are demonstrated. The substrate effect on device operation is measured and modeled; methods for utilizing the substrate effect to tune device operation are presented. Later devices are fabricated using the SUMMiT process. Changes in the SUMMiT design rules to increase allowable vertical motion range are proposed and designs using them fabricated. S-parameter characteristics of devices in both `on' and `off' states are measured. Addition of metallization after chip fabrication and release is necessary to lower the resistance of interconnect. A self masking method for applying this metallization allowing for decreased resistance at line crossings is proposed. This method is tested using each of sputtering and evaporation as the deposition technique for a gold and adhesion layer stack. Effectiveness of the method with each technique is evaluated. Chips suitable for providing high voltage control for large MEMS arrays are fabricated in a 2um feature size CMOS process. Architectures suitable for building large crossbars employing variable capacitor arrays are discussed. Optimization of hybrid CMOS/MEMS Clos arrays on the basis of criteria other than minimization of crosspoints is discussed. Array sizings to provide 192*192 and 256*256 crossbars are presented, and software examples for sizing and controlling Clos networks are provided. Evaluation of the suitability of the MEMS devices developed for use as digital or broadband crosspoints is evaluated, and potential future directions are proposed. <P>
|
60 |
SCALABLE DISTRIBUTED TUPLESPACESNemlekar, Milind 05 December 2001 (has links)
<p><P><B>NEMLEKAR, MILIND NILKANTH. Scalable Distributed Tuplespaces. (Under the direction of Dr. Gregory T. Byrd.)</B></P><P>The purpose of the research has been to develop a multiple tuplespace model that would scale as much as the Internet. A tuplespace is like a shared cache, in which tuples are accessed associatively. One issue in designing a multiple tuplespaces model is keeping track of tuples over multiple space servers. Since, replication is used to reduce access latencies to tuples, another issue is of establishing coherency of replicas and consistency of tuplespace operations over multiple replicas.</P><P>The thesis looks at design of a hierarchical directory structure over a flat organization of tuplespaces, which addresses the above issues. With this model scalable protocols are proposed that keep track of tuples/templates among multiple nodes, and establish coherency of tuple replicas.</P><P>A prototype of this model has been implemented within the Jini<P>
|
Page generated in 0.0583 seconds