bluuebunny/crossref_metadata_2025 huggingface dataset:
Coping with network failures
Authors: Applegate David , Breslau Lee , Cohen Edith
Published: January 2007

Link and node failures in IP networks pose a challenge for network control algorithms. Routing restoration, which computes new routes that avoid failed links, involves fundamental tradeoffs between efficient use of network resources, complexity of the restoration strategy and disruption to network traffic. In order to achieve a balance between these goals, obtaining routings that provide good performance guarantees under failures is desirable.In this paper, building on previous work that provided performance guarantees under uncertain (and potentially unknown) traffic demands, we develop algorithms for computing optimal restoration paths and a methodology for evaluating the performance guarantees of routing under failures. We then study the performance of route restoration on a diverse collection of ISP networks. Our evaluation uses a competitive analysis type framework, where performance of routing with restoration paths under failures is compared to the best possible performance on the failed network. We conclude that with careful selection of restoration paths one can obtain restoration strategies that retain nearly optimal performance on the failed network while minimizing disruptions to traffic flows that did not traverse the failed parts of the network.
The impact of BGP dynamics on intra-domain traffic
Authors: Agarwal Sharad , Chuah Chen-Nee , Bhattacharyya Supratik , Diot Christophe
Published: January 2007

Recent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered the impact of inter-domain routing changes in BGP (Border Gateway Protocol). BGP routing changes have the potential to introduce significant errors in estimated traffic matrices by causing traffic shifts between egress routers or PoPs within a single backbone network. We present a methodology to correlate BGP routing table changes with packet traces in order to analyze how BGP dynamics affect traffic fan-out within a large "tier-1" network. Despite an average of 133 BGP routing updates per minute, we find that BGP routing changes do not cause more than 0.03% of ingress traffic to shift between egress PoPs. This limited impact is mostly due to the relative stability of network prefixes that receive the majority of traffic -- 0.05% of BGP routing table changes affect intra-domain routes for prefixes that carry 80% of the traffic. Thus our work validates an important assumption underlying existing techniques for traffic matrix estimation in large IP networks.
A model of BGP routing for network engineering
Authors: Feamster Nick , Winick Jared , Rexford Jennifer
Published: January 2007

The performance of IP networks depends on a wide variety of dynamic conditions. Traffic shifts, equipment failures, planned maintenance, and topology changes in other parts of the Internet can all degrade performance. To maintain good performance, network operators must continually reconfigure the routing protocols. Operators configure BGP to control how traffic flows to neighboring Autonomous Systems (ASes), as well as how traffic traverses their networks. However, because BGP route selection is distributed, indirectly controlled by configurable policies, and influenced by complex interactions with intradomain routing protocols, operators cannot predict how a particular BGP configuration would behave in practice. To avoid inadvertently degrading network performance, operators need to evaluate the effects of configuration changesbefore deploying them on a live network. We propose an algorithm that computes the outcome of the BGP route selection process for each router in asingleAS, given only a static snapshot of the network state, without simulating the complex details of BGP message passing. We describe a BGP emulator based on this algorithm; the emulator exploits the unique characteristics of routing data to reduce computational overhead. Using data from a large ISP, we show that the emulator correctly computes BGP routing decisions and has a running time that is acceptable for many tasks, such as traffic engineering and capacity planning.
Harpoon
Authors: Sommers Joel , Kim Hyungsuk , Barford Paul
Published: January 2007

We describe Harpoon, a new application-independent tool for generating representative packet traffic at the
IP flow level
. Harpoon is a configurable tool for creating TCP and UDP packet flows that have the same byte, packet, temporal, and spatial characteristics as measured at routers in live environments. We validate Harpoon using traces collected from a live router and then demonstrate its capabilities in a series of router performance benchmark tests.
Using probabilistic reasoning to automate software tuning
Authors: Sullivan David G. , Seltzer Margo I. , Pfeffer Avi
Published: January 2007

Manually tuning the parameters or "knobs" of a complex software system is an extremely difficult task. Ideally, the process of software tuning should be automated, allowing software systems to reconfigure themselves as needed in response to changing conditions. We present a methodology that uses a probabilistic, graphical model known as an influence diagram as the foundation of an effective, automated approach to software tuning. We have used our methodology to simultaneously tune four knobs from the Berkeley DB embedded database system, and our results show that an influence diagram can effectively generalize from training data for this domain.
The origins of network server latency & the myth of connection scheduling
Authors: Ruan Yaoping , Pai Vivek S.
Published: January 2007

We investigate the origins of server-induced latency to understand how to improve latency optimization techniques. Using the Flash Web server [4], we analyze latency behavior under various loads. Despite latency profiles that suggest standard queuing delays, we find that most latency actually originates from negative interactions between the application and the locking and blocking mechanisms in the kernel. Modifying the server and kernel to avoid these problems yields both qualitative and quantitative changes in the latency profiles -- latency drops by more than an order of magnitude, and the effective service discipline also improves.We find our modifications also mitigate service burstiness in the application, reducing the event queue lengths dramatically and eliminating any benefit from application-level connection scheduling. We identify one remaining source of unfairness, related to competition in the networking stack. We show that adjusting the TCP congestion window size addresses this problem, reducing latency by an additional factor of three.
Statistical behavior of fast hashing of variable length test strings
Authors: Savoy Jacques
Published: January 2007

In information retrieval, we often have to store and search for a particular record into a large amount of information. For example, during a document indexing process or when a program is trying to spell a text, a dictionary has to be used in an efficient way. A solution to that problem resides in using a hash table. However, if we known many algorithms for manipulating or accessing hash tables [Knuth 73], [Standish 80], [Wiederhold 87], the main problem is to define a "good" hash function for a variable-length string. In order to answer that question our main goals are to present some concrete algorithms and to study their statistical behavior.
Book review: An Introduction to Text Processing by Peter D. Smith. The MIT Press, Cambridge, Massachusetts, 1990, 300 pp., $32.50, ISBN 0-262-19299-3
Authors: Can Fazli
Published: January 2007

There are very few books on text processing, Recently I performed a search on the CD version of the Books in Print Plus, which is the master reference to currently available books, authors, and publishers in the US. I found just fifty books that contain the words "text" and "processing," and fourteen books that contain "document" and "processing" in their titles. (As a side light and for comparison: there are 644 books containing "information" and "retrieval" in their titles.) This book is a survey of text processing applications, and algorithms; a welcome addition to the literature.
Approximate MVA solutions with fixed throughput classes
Authors: Allen Arnold O. , Hynes Gary
Published: January 2007

Transaction (open) type workloads are often used in approximating computer system workloads which are actually closed because open workloads provide reasonable estimates in many cases and their solutions are straight-forward. We have found that their use can distort the results for many workloads in a multiclass queueing network model of a computer system. We have replaced transaction workloads with what we call
fixed class
workloads. We present an approximate algorithm based on MVA that represents a class with a given throughput by a corresponding terminal or batch class, which we call a fixed class workload. We solve for the closed population required to deliver the requested throughput. We also present techniques for overcoming problems encountered in the solution of some fixed class models.
Dynamic clustering procedures for bibliographic data
Authors: Kambayashi Yahiko , Hayashi Takaki , Yajima Shuzo
Published: January 2007

Clustering is an important tool for efficient retrieval of documents in bibliographic database systems. It can be also used to find research trend from a set of research papers. This paper discusses new clustering procedures called dynamic ones which seem to be suitable for bibliographic data handling. These procedures are developed to solve the following problems.(1) Depending on the characteristics of data, several different clustering procedures are required to obtain good results.(2) Large clusters are tend to be generated.Dynamic clustering procedures are difined to be procedures which change parameter values according to the characteristics of data. Similarity values and threshold values are dynamically modified to handle the above problems. Furthermore, to treat the latter problem data duplication is considered.
Spatial representations of knowledge
Authors: Noreault Terry , Dovidio John F.
Published: January 2007

This research examined the relationship between subjects' knowledge of an area and their similarity ratings of pairs of concepts. Knowledge was operationalized as (1) test score performance, and (2) correspondence with an expert's similarity judgments. Subjects (n=55) were exposed to a three-week module on social psychology as part of their introductory psychology course. At the end of this course segment they were administered an examination and, later, a term similarity questionnaire. Students' similarity ratings related to both exam score and similarity ratings of the expert. Furthermore, as expected, test performance was strongly related (r=+.55) to the correlation with the expert's similarity judgments. A model based on term similarity judgments was proposed as a theoretical explanation of how term dependence models influence information retrieval system performance.
End user behavior on an online information retrieval system
Authors: Borgman Christine L.
Published: January 2007

We report on a computer monitoring study of users of the Ohio State University Libraries' online catalog, an established and heavily used information retrieval system. To our knowledge, this is the first monitoring study of an online catalog performed without system-defined user sessions. Online catalogs represent a class of retrieval systems which are designed for end users, require little or no formal training, and replace an existing manual system. The study characterizes user behavior in terms of types of searches done, patterns of use, time spent on searching, errors, and system problems. Preliminary results suggest that users have much shorter sessions than on other types of retrieval systems. Patterns of use vary between campus libraries, academic quarters, and between short and long sessions. Results of the study will be applied to improving the user interface and other system features.
RESEDA, an Information Retrieval system using artificial intelligence and knowledge representation techniques
Authors: Zarri Gian Piero
Published: January 2007

The RESEDA project is concerned with the construction of AI Information Retrieval systems working on databases containing biographical data. There exist in RESEDA two fundamental ways of retrieving information requested by a user. In the first case, the information we wish to obtain is data which already exists in the base. This data can be obtained by direct match with the "search model" corresponding to the user's question. If this is not possible, we can still try to get an answer by using the inference procedures of the "transformation" type. The second method retrieves information which, in contrast, is created ex nihilo by the search procedure itself. It expresses, in fact, the possibility of a new causal relationship, within the base, between an "episode" provided explicitly by the user and one or more "episodes" that the system retrieves by applying an inference procedure of the type "hypothesis".
Current practice in the evaluation of multikey search algorithms
Authors: Eastman C. M.
Published: January 2007

File structures and algorithms for multikey searching allow more than a single key to be used in locating a record for use in retrieval or update. Such algorithms are of use in many different kinds of information systems, including database systems, information retrieval systems, and pattern recognition and image processing systems. Such algorithms have received increased attention in recent years. However, they are not as well understood as those which handle single keys.Multikey algorithms are more difficult to evaluate than those based on the use of single keys. There are simply more factors to be considered. The evaluations performed for such algorithms should allow comparisons in order to be useful to a community of researchers and users. Theoretical analyses should be based on reasonable and clearly stated assumptions. Experiments should be repeatable and statistically valid whether they are based on "real" data or on randomly generated data.
A clustering strategy based on a formalism of the reproductive process in natural systems
Authors: Raghavan Vijay V. , Birchard Kim
Published: January 2007

Given a set of objects each of which is represented by a finite number of attributes or features and a clustering criterion that associates a value of utility to any classification, the objective of a clustering method is to identify that classification of the objects which optimizes the criterion. A new strategy to solve this problem is developed. The approach is, in essence, a modification of the reproductive plan, a type of adaptive procedure devised by Holland [2], which embodies many principles found in the adaptation of natural systems through evolution. The proposed approach differs from conventional methods in the sense that the search through the space of possible solutions proceeds in a parallel fashion.The adaptive clustering strategy requires the specification of methods for the generation of an initial population of classifications, the parent selection, the modifications and the replacement of current classifications with new ones. The effects of changing several of these features are investigated. Experimental results show that it is possible to devise clustering strategies based on the principles of adaptation in natural systems that are both effective and efficient.
The economic implementation of experimental retrieval techniques on a very large scale using an intelligent terminal
Authors: Jamieson S. H.
Published: January 2007

The results and achievements of research in information retrieval have had little influence on the types of retrieval mechanism implemented in the large commercial on-line retrieval systems. Commercial systems still use simple Boolean techniques while experiments have shown that other techniques, such as those making use of relevance information, perform better. Reasons for this are suggested. A strategy is described for the implementation of high-powered techniques which overcomes this problem - an intelligent terminal is used in conjunction with an existing commercial I. R. system. The added processing capability permits the implementation of more sophisticated retrieval techniques very cheaply. Retrieval methods that can be implemented on such a terminal used in this way are described.Particular emphasis is placed upon the practical implementation of a term weighting scheme based on relevance feedback information which generates a ranked list of documents in answer to a query.
The role of information retrieval in the second computer revolution
Authors: Wiersba R. K.
Published: January 2007

Information retrieval is conceptually fundamental in human communication as well as in man-computer communication. Computing and Information Retrieval professionals have the opportunity to apply information retrieval techniques within the second computer revolution to foster a new potential revolution in education, brought about by the advent of the personal computer.
A Block Structured Query Language for accessing a relational data base
Authors: Baxter Anthony Q. , Johnson Rowland R.
Published: January 2007

This paper describes a
B
lock
S
tructured
Q
uery
L
anguage (BSQL) to be used with relational data bases. The syntax of the language is presented and discussed. Facilities of the language are illustrated by examples of actual queries. In particular we demonstrate the ability of BSQL to obtain useful information from a relational data base that is incomplete. A relational calculus is then presented which forms a basis for a formalism which precisely describes the semantics of BSQL. Finally, comparative examples with other query languages are given.
Book review: Blackboard Architectures and Applications Edited by V. Jagannathan, Rajendra Dodhiawala, and Lawrence S. Baum (Academic Press)
Authors: Watson David E.
Published: January 2007

The recent publication of two books on blackboard architectures,
Blackboard Architectures and Applications
(eds. V. Jagannathan, R. Dodhiawala, and L.S. Baum, Academic Press, Inc., 1989) and
Blackboard Systems
(eds. R. Engelmore and T. Morgan, Addison Wesley, 1988) is an indication of the maturity and current popularity of this particular area of AI research.
Blackboard Architectures and Applications,
the book under review here, is the most current of these two works.
Book review: Developing and Managing Expert Systems by David S. Prerau (Addison Wesley)
Authors: Norton Philip
Published: January 2007

This book provides a step by step approach to developing and managing expert systems. The text thoroughly covers all of the proven techniques used in each step of the development process and provides very pragmatic advice covering typical problems faced with building expert systems. One common weakness of many business oriented expert systems texts is that they provide a general listing of expert system examples and usually end up focusing on system that the typical business person cannot relate to. A case in point is Waterman's
A Guide to Expert Systems
and James Martin's
Expert Systems: A Tutorial.
Both texts are adequate beginner texts, but Waterman devotes too much attention to Prospector, and expert system for geologists, while Martin provides a lengthy overview of different systems that are available. These exhaustive lists, with descriptions of various expert systems, in a multitude of fields, usually overwhelm the reader with triviality. This information is quickly outdated and rarely provides the reader with any lasting knowledge.
An analysis of central processor-input-output processor contention
Authors: Strecker William D.
Published: January 2007

Most computer systems have separate central (CPU) and input-output (IOP) processors to permit simultaneous computation and input-output (I/O). It is conventional in such systems to avoid any loss of I/O data by granting the IOP priority over the CPU for memory service. Although this priority discipline is simple to implement it may result in a maximum degradation of CPU performance. In this discussion an analysis of the IOP priority discipline is given together with an analysis of other priority disciplines which require the buffering of IOP requests and results are given showing that only a small amount of buffering is required to produce a noticeable improvement in CPU performance.
The benchmarking, tuning and analytic modeling of VAX/VMS
Authors: Lazowska Edward D.
Published: January 2007

This paper describes a recent experience in benchmarking, tuning and modelling Digital Equipment Corporation's VMS executive running on their VAX-11/780 computer. Although we emphasize modelling here, the three aspects are closely interrelated.
Modeling and simulating data flow computations at machine language level
Authors: Yu Stone H. , Murata Tadao
Published: January 2007

This paper is concerned with the data flow organization of computers and programs, which exhibits a good deal of inherent concurrencies in a computation by imposing no superfluous precedence constraints. In view of the popularity of parallel and distributed processing, this organization can be expected to play an increasingly prominent role in the design and development of computer systems. A schematic diagram called DF-graphs, suitable for modeling data flow computations at the machine language level, is introduced. To facilitate the storage of DF-graphs in computers, matrix equations which fully describe their structure and their dynamic behaviors are developed as an alternate representation. Also demonstrated is the feasibility of simulating the execution of computations specified by DF-graphs on a network of conventional mini- and microprocessors.
Criteria for computer performance analysis
Authors: Dujomović Jozo J.
Published: January 2007

Computer evaluation, comparison, and selection is essentially a decision process. The decision making is based on a number of worth indicators, including various computer performance indicators. The performance indicators are obtained through the computer performance measurement procedure. Consequently, this procedure should be completely conditioned by the decision process.

This paper investigates various aspects of computer performance measurement and evaluation procedure within the context of computer evaluation, comparison and selection process based on the Logic Scoring of Preference method. The set of elementary criteria for performance evaluation is proposed and the corresponding set of performance indicators is defined. The necessary performance measurements are based on the standardized set of synthetic benchmark programs and include three separate measurements: monoprogramming performance measurement, multiprogramming performance measurement, and multiprogramming efficiency measurement. Using the proposed elementary criteria, the measured performance indicators can be transformed into elementary preferences and aggregated with other non-performance elementary preferences obtained through the evaluation process. The applicability of presented elementary criteria is illustrated by numerical examples.
An introduction to the simulation of a multiple CPU military communications system
Authors: Sprung James G. , Beatty Paul T. , Camery John W. , Norrell John C.
Published: January 2007

All telecommunication systems design, development and support for the Headquarters, Department of the Army, is provided by the Automation Support Detachment. The current operational telecommunication system provides the Army with a full range of communication functions, i.e., receipt, transmission, message validation and online CRT operations, on a dedicated IBM System/360 (Model 50) processor. The system is designed to handle 1500 messages per hour with an average message size of 2000 characters operating on a round-the-clock basis.

Design efforts are currently underway to extend the capabilities of the present system and to provide similar operational services to all communication centers within the Pentagon. The proposed system will include a mixture of minicomputers and an IBM System/360 (Model 65) and will support a workload of 6000 messages per hour. The design effort involves computer simulation of the proposed system.

This paper describes the development of a comprehensive “system” of three models which represent the Front End Control, Message Processing, and Staff Service Center Subsystems. These models are written in ECSS II and are linked by special message generation modules. The special processing requirements as well as the multiple CPU configuration present some unique modeling situations.

The form the model has taken is predicated to a large extent, on the available data. Extensive use is made of hardware and software monitoring of the IBM System/360 (Model 50) and the analysis of message traffic statistics. The modeling of the traffic statistics. The modeling of the input processing is statistically related to the output processing The processing is functionally divided into stages to provide a high level of generality for the models and add uniformity throughout the models. Various simulation statistics are gathered for each stage besides the usual ECSS II generated statistics.

Model validation techniques and future uses of the model are described. A discussion of specific simulation techniques and outputs is beyond the scope of this overview document and, therefore, is deferred to future papers.
A Diagnostic Emulator for HEAO software development
Authors: Beer Peter H. , Hupf Kenneth J.
Published: January 2007

Diagnostic Emulation is the application of microprogramming to the emulation of an operational computer to support software development and verification for that computer. A conventional technique, Interpretive Computer Simulation (ICS), has been used for many years in support of such software development and verification efforts. The ICS method is becoming less cost effective. For the development of attitude control software for NASA's High Energy Astronomical Observatory (HEAO) diagnostic emulation was considered as an alternative.

This paper describes the motivation for using an ICS or diagnostic emulator to validate command and control software, the potential advantages of microprogramming, and the analysis which led to the development of the HEAO Diagnostic Emulator rather than the use of conventional techniques. Also discussed are the emulator implementation tradeoff analysis, the resulting program design, and the interface between the microprogram and the assembly language modules. The results to date are described, including the capability, speed, and reliability of the program and initial user response.
A Fortran to C converter
Authors: Feldman S. I.
Published: January 2007

We have produced a program that automatically converts ANSI standard Fortran 77 [1] to C [8]. It has converted many Fortran programs without manual intervention; it is easily available --- free of charge (and of warranty) --- by electronic mail and
ftp.
What if mass storage were free?
Authors: Copeland George
Published: January 2007

This paper investigates how database systems would be designed and used under the limiting-case assumption that mass storage is free. It is argued that free mass storage would free database systems from the limitations and problems caused by conventional deletion techniques. A non-deletion strategy would significantly simplify database systems and their operation, as well as increase their functionality and availability. Consideration of this limiting case helps shed light on a more realistic argument: if the cost of mass storage were low enough, then deletion would become undesirable.

It is also argued that the often labor-intensive costs and time delays involved in archival and retrieval of older data can be minimized if a single technology were available with low-cost on-line storage and a low-cost archival media with long shelf life.

Optical discs promise to come one to two orders of magnitude closer to the limiting case of free mass storage than ever before. Other features of optical discs include improved reliability and a single technology for both on-line and archival storage with a long shelf life. Because of these features and because of (not in spite of) their non-deletion limitation, it is argued that optical discs fit the requirements of database systems better than magnetic discs and tapes.
Evaluation of alternate data base machine designs
Authors: Vemuri V. , Liuzzi R. A. , Cavano J. P. , Berra P. B.
Published: January 2007

The purpose of this paper is to point out the need for performance evaluation measures and techniques suitable for the evaluation of specialized architectural features in nonnumeric applications. Toward this end, problems associated with the use of data base machines are examined at three levels of detail: the user level, the system level and the device level.
Fifth workshop on computer architecture for non-numeric processing
Authors: Poon Ronnie K. L. , Wong Kwan Y.
Published: January 2007

The purpose of this short paper is to describe some activities in our laboratory on designing a flexible image processor using array processing elements. In many document creation applications, it is desirable to include image handling capability in the system together with keystroke captured text processing function. However, this image handling creates two problems: one is the large amount of data needed for image storage, and the other is the large amount of processing required to produce an output image. Data compression reduces storage and transmission bandwidth requirements, but it also requires processing power to do compression and de-compression of images. The objective of the study is to provide low-cost hardware which has the flexibility to do a variety of image processing algorithms.
Global optimization of microprograms through modular control constructs
Authors: Wood Graham
Published: January 2007

By taking due regard of the disciplines of structured programming, we extend the scope of optimization of microprograms from blocks of micro-operations delimited by labels and branches (straight line segments) to complete microprograms.
Design and implementation of a flexible and interactive microprogram simulator
Authors: Mezzalama M. , Prinetto P.
Published: January 2007

In the present paper a microprogrammable architecture oriented simulator is described. This simulator structure may be logically subdivided in four independent blocks: Supervisor, Interface Module, Simulation Monitor, Simulation Routines.

A high degree of flexibility is obtained by means of a highly hierarchical structure of software and an easy-to-modify table-driven system description. Moreover particular care has been devoted to user-simulator communication via an easy-to-use command language. The use of the simulator in the development of a microprogrammable machine (based on Am2900 bit-slice microprocessors) is described.
Interactive microprogram validation
Authors: Crews Phillip , Leventhal Laura Marie
Published: January 2007

This paper presents a solution to the problem of an inadequate microprogram testbed facility for the Prime 400 system, but more importantly, defines typical problems resulting from lack of good microprogram developement software in the university environment, and provides a model for their solution.
A microcoded tool to sample the software instruction address
Authors: Armbruster C. Edward
Published: January 2007

This paper introduces the concept of software execution localization and defines a microcoded tool for measuring execution localization. The tool is presented as a conceptual description.

This tool has been used during development of microcode assists for the System/370 Models 138 and 148, and also the 4341 Processor.
Direct architectural implementation of a requirements-oriented computing structure
Authors: Anastas M. S. , Vaughan R. F.
Published: January 2007

Many of the advances in computing technology that have a direct bearing on software productivity have been integrated into a unique requirements-oriented computing structure devoid of transfer of control constructs. Overhead is a major obstacle to such a structure. A computer architecture based on this structure is therefore derived for which combinational logic can be used to solve this overhead problem. A family of computers called Transition Machines is thereby defined which addresses many of the major problem areas affecting software productivity.
I/O device Emulation in The Stanford Emulation Laboratory
Authors: Huck Jerry , Neuhauser Charles
Published: January 2007

This report describes the implementation of an I/O device emulation system for a universal host machine, the Emmy. The actual system I/O devices are part of a PDP-11/05 system supporting the UNIX operating system. To support device emulation a process is established within this system to act as a simple I/O channel responding to host I/O requests. This channel process is able to provide three basic device structures: serial, linear and variable, which correspond roughly to character, disk-like and tape-like devices respectively. These structures have been found to be adequate for a wide range of system emulations. Examples of such systems and their performance are given.
The role of software tools in the development of the ECLIPSE® MV/8000 microcode
Authors: Firth Neal R.
Published: January 2007

This paper presents an overview of the software tools used in the development of the microcode for Data General's new 32 bit processor the ECLIPSE MV/8000. Included in this overview is a brief description of each of the tools, and the design philosophies used during their development.
2
n
-way jump microinstruction hardware and an effective instruction binding method
Authors: Fisher Joseph A.
Published: January 2007

A scheme is developed by which multiway microprogram jumps may be made to any of 2
n
next possible microinstructions as a function of any selection of n > 1 logically independent tests. An efficient method of binding microinstructions to memory locations allows this to be done at very low cost, both in terms of speed and hardware.

Independent simultaneous tests are a necessity if horizontally microcodable machines are to continue to get wider, since algorithms presumably have fixed operations/tests ratios. This scheme will give parallelizers for such machines maximum flexibility in rearranging flow control.
A survey of high level microprogramming languages
Authors: Sint Marleen
Published: January 2007

This paper surveys the current state of design and implementation of high level microprogramming languages. First, a number of important design issues are formulated. Next, four microprogramming languages are considered in detail, to see how each of them has approached these issues. Brief remarks are made about six other languages. Finally, some concluding remarks are made.
A meta-assembler for highly-parallel microprogrammable systems
Authors: Berglass Gilbert R.
Published: January 2007

This paper describes a software system whose input is a description of a highly parallel (horizontally) microprogrammable machine as reflected in the organization of the machine's “word” and a set of user-specified statement “patterns” defining the microprogramming language. Programs in the user-defined language are assembled into relocatable segments, which are linked together by a loader to form object modules. This design has proved effective in an environment where a group of engineers and programmers were involved in the programming of several architecturally different components for the emulation of the IBM System/370 on the NANODATA QMX.
Monte Carlo techniques in code optimization
Authors: Jacobs Dean , Prins Jan , Siegel Peter , Wilson Kenneth
Published: January 2007

Effective optimization of FPS Array Processor assembly language (APAL) is difficult. Instructions must be rearranged and consolidated to minimize periods during which the functional units remain idle or perform unnecessary tasks. Register conflicts and branches cause complications. Deterministic algorithms to arrange instructions traditionally use complex heuristics which are tailored to specific inputs. A non-deterministic approach can be simpler and effective on a large class of inputs. This is a progress report on the “Monte Carlo” optimizer under construction at Cornell University by the authors. This optimizer randomly modifies the text of an APAL program without changing its meaning. Modifications which improve the program are favored. A set of six elementary transformations are the basis for modifications.
EASY—an operating system for the QM-1
Authors: Flink Charles W.
Published: January 2007

The Emulation Aid SYstem is a virtual machine monitor for the Nanodata QM-1 microprogrammable computer. The system is designed to provide the user with an interactive interface for the development and subsequent use of emulations on the QM-1. EASY provides integrated support for: 1) interactive control of multiple, concurrently resident, virtual computers implemented via emulation, 2) input/output from emulations (virtual I/O) to the various real peripherals of the QM-1, and 3) diagnostic displays for debugging of both the emulations and the software running on the emulated computers. EASY is implemented at three distinct levels: the majority of the system software is programmed in a high-level language (SIMPL-Q); this (service) software, in turn, executes on an emulated intermediate language machine (also called EASY); the EASY machine executes as the highest priority task under a microprogrammed operating system kernel (called TASK). Via EASY the user currently has access to several previously developed emulations. EASY is the host system for ongoing emulator development at the Navy's Dahlgren Laboratory.
An approach to microprogram optimization considering resource occupancy and instruction formats
Authors: Tokoro Mario , Tamura Eiji , Takase Kazuhiko , Tamaru Kiichiro
Published: January 2007

This paper describes a microprogram optimization technique considering resource occupancy and microinstruction format. This technique is applicable to machines whose microoperation occupies several machine cycles on a submachine cycle basis, and whose microinstruction format varies from horizontal to partially encoded, to vertical. “Microtemplate” is proposed to represent fetch timing and period of resource usage for a microoperation on a machine cycle and submachine cycle basis. An algorithm is shown, which detects concurrency of sequentially written microoperations through manipulation of microtemplates. An algorithm of microinstruction format selection is also discussed which decides one instruction format when several candidates exist. Effectiveness of this technique is evaluated. Efficient object codes are generated when applied to a practical sophisticated microprogrammable computer.
MICROSIM
Authors: Mathur Francis P.
Published: January 2007

This paper describes in the format of a user's manual, along with an example, a program for teaching microprogramming and emulation. This program simulates at the microinstruction set level the architecture of a 16-bit microprogram-controlled minicomputer. This simulator, as an instructional vehicle, has been successfully used in a software engineering laboratory adjunct to a regular course in microprogramming and computer architecture.
Microprogrammed implementation of a single chip microprocessor
Authors: Stritter Skip , Tredennick Nick
Published: January 2007

This paper considers microprogramming as a tool for implementing large scale integration, single-chip microprocessors. Design trade-offs for microprogrammed control are discussed in the context of semiconductor design constraints which limit the size, speed, complexity and pin-out of circuits. Aspects of the control unit of a new generation microprocessor, which has a two level microprogrammed structure, are presented.
A technique of global optimization of microprograms
Authors: Tokoro Mario , Takizuka Takashi , Tamura Eiji , Yamaura Ichiro
Published: January 2007

This paper describes a technique of global optimization of microprograms including loops and recursive subroutines. This technique can be applied to a wide variety of microprogrammable machines. The principle of global optimization, four basic types of global optimization, and extended types of global optimization are discussed and the optimization algorithm is shown. Its effectiveness is evaluated and confirmed by applying it to an existing microprogrammable computer composed of LSI processor modules.
Recent progress in the performance evaluation of fundamental allocation algorithms
Authors: Coffman E. G.
Published: January 2007

Our understanding of several allocation algorithms basic to operating systems and to data base systems has improved substantially as a result of a number of research efforts within the past one or two years. The results have stirred considerable excitement in both theorists and practitioners. This is not only because of the inroads made into long-standing problems, but also because of the surprising nature of the results; in particular, we refer to proofs that certain classical algorithms described as approximate are in fact optimal in a strong probabilistic sense.

The work discussed here will be classified according to the application areas, archival and dynamic storage allocation. In both cases we are concerned with the packing problems that arise in making efficient use of storage. Equivalents of the archival problems also have importance in scheduling applications [4]; however, we shall focus exclusively on the storage allocation setting.
Parameter interdependencies of file placement models in a Unix system
Authors: Perez-Davila Alfredo de J. , Dowdy Lawrence W.
Published: January 2007

A file assignment case study of a computer system running Unix is presented. A queueing network model of the system is constructed and validated. A modeling technique for the movement of files between and within disks is proposed. A detailed queueing network model is constructed for several file distributions in secondary storage. The interdependencies between the speed of the
CPU
, the swapping activity, the visit ratios and the multiprogramming level are examined and included in the modeling technique. The models predict the performance of several possible file assignments. The various file assignments are implemented and comparisons between the predicted and actual performance are made. The models are shown to accurately predict user response time.
A new 'building block' for performance evaluation of queueing networks with finite buffers
Authors: Suri Rajan , Diehl Gregory W.
Published: January 2007

We propose a new 'building block', for analyzing queueing networks. This is a model of a server with a variable buffer-size. Such a model enables efficient analysis of certain queueing networks with blocking due to limited buffer spaces, since it uses only product-form submodels. The technique is extensively tested, and found to be reasonably accurate over a wide range of parameters. Several examples are given, illustrating practical situations for which our model would prove to be a useful performance analysis tool, specially since it is simple to understand, and easy to implement using standard software for closed queueing networks.
Analysis of Queueing Network Models with population size constraints and delayed blocked customers
Authors: Thomasian Alexander , Bay Paul
Published: January 2007

Queueing Network Models - QNM's with population size constraints and delayed blocked customers occur due to MultiProgramming Level - MPL constraints in computer systems and window flow-control mechanisms in Computer Communication Networks - CCN's. The computational cost of existing algorithms is unacceptable for large numbers of chains and high population sizes. A fast approximate solution technique based on load concealment is presented to solve such QNM's. The solution procedure is non-iterative in the case of fixed rate Poisson arrivals, while iteration is required in the case of quasi-random arrivals. Each iteration requires the solution of a single chain network of queues comprised of stations visited by each chain. We then present an algorithm to detect saturated chains and determine their maximum throughput. A fast solution algorithm due to Reiser for closed chains is also extended to the case of quasi-random arrivals. The accuracy of the proposed solution techniques is compared to previous techniques by applying it to a test case, reported in the literature, and a set of randomly generated examples.
Reactive maintenance of continuous queries
Authors: Trajcevski Goce , Scheuermann Peter
Published: January 2007

This work addresses the problem of maintaining the consistency of the answers to continuous queries which are posed by the users of the Moving Objects Databases (MOD). Assuming that the motion of the object is represented by a trajectory, we focus on the effect that the modifications to the trajectory data can have on the queries answer-set. In case a mobile user enters a road section in which an accident has occurred, which was not anticipated in the "expected" traffic behavior, not only his trajectory needs to updated, but the answer to the query that he posed may need to be recalculated and transmitted again. In this work we propose a framework which enables detecting and processing the pending queries whose answers need to be re-evaluated upon modifications to the MOD. We identify the relevant syntactic elements which can be extracted from the user's queries and we analyze their semantic implications. We also propose an architecture of a system that can be used for this task. We demonstrate how triggers can be used to maintain the answers to the users' queries "up to date" with respect to the modifications to the MOD and we show that our framework can be implemented on top of the existing ORDBMS.
Reading temporally consistent data in broadcast disks
Authors: Lee Victor C. S. , Ng Joseph K. , Chong Jo Y. P. , Lam Kwok-wa
Published: January 2007

In this paper, we study the performance and impact of maintaining temporal consistency on a recently proposed concurrency control protocol for processing transactions in broadcast environments. This protocol offers autonomy between mobile clients and the server such that mobile clients can read consistent data off the air without contacting the server. However, most of the existing mobile computing applications, such as information dispersal systems for stock prices and weather information, are comprised of real-time read only transactions. In order to deliver timely and useful results, real-time transactions must read temporal consistent data in addition to completing the execution before their deadlines. A number of approaches to maintaining temporal consistency are studied through a series of simulation experiments. Results show that taking advantage of data semantics and temporal consistency requirement can improve the performance of mobile read only transactions in broadcast environments.
A general distribution formula of the count of mobiles crossing location areas between two data traffic arrivals
Authors: Xiong Yong , Bu Zhiyong
Published: January 2007

Location management is a challenging part in mobile communication. Studying the situation that the count of mobiles crossing location areas between two data traffic arrivals is significant to evaluate the costs and performances of various location management strategies, when 4G mobile communication faces vast data traffic. In this paper, we propose a new model for mobile terminal movement in personal communications services networks. Based on this model with Markov arrival process for data traffic arrival process to mobile terminal, general distribution time the mobile terminal resides in LAo, another general distribution time the mobile terminal resides in LAn, by using density evolution method, we present a general distribution formula of the count of mobiles crossing location areas between two successive data traffic arrivals.