bluuebunny/crossref_metadata_2025 huggingface dataset:
Bridging router performance and queuing theory
Authors: Hohn N. , Veitch D. , Papagiannaki K. , Diot C.
Published: January 2007

This paper provides an authoritative knowledge of through-router packet delays and therefore a better understanding of data network performance. Thanks to a unique experimental setup, we capture
all
packets crossing a router for 13 hours and present detailed statistics of their delays. These measurements allow us to build the following physical model for router performance: each packet experiences a minimum router processing time before entering a fluid output queue. Although simple, this model reproduces the router behaviour with excellent accuracy and avoids two common pitfalls. First we show that in-router packet processing time accounts for a significant portion of the overall packet delay and should not be neglected. Second we point out that one should fully understand both link and physical layer characteristics to use the appropriate bandwidth value.Focusing directly on router performance, we provide insights into system busy periods and show precisely how queues build up inside a router. We explain why current practices for inferring delays based on average utilization have fundamental problems, and propose an alternative solution to directly report router delay information based on busy period statistics.
Insensitive load balancing
Authors: Bonald T. , Jonckheere M. , Proutiére A.
Published: January 2007

A large variety of communication systems, including telephone and data networks, can be represented by so-called Whittle networks. The stationary distribution of these networks is insensitive, depending on the service requirements at each node through their mean only. These models are of considerable practical interest as derived engineering rules are robust to the evolution of traffic characteristics. In this paper we relax the usual assumption of static routing and address the issue of dynamic load balancing. Specifically, we identify the class of load balancing policies which preserve insensitivity and characterize optimal strategies in some specific cases. Analytical results are illustrated numerically on a number of toy network examples.
Wireless data performance in multi-cell scenarios
Authors: Bonald T. , Borst S. , Hegde N. , Proutiére A.
Published: January 2007

The performance of wireless data systems has been extensively studied in the context of a single base station. In the present paper we investigate the flow-level performance in networks with multiple base stations. We specifically examine the complex, dynamic interaction of the number of active flows in the various cells introduced by the strong impact of interference between neighboring base stations. For the downlink data transmissions that we consider, lower service rates caused by increased interference from neighboring base stations result in longer delays and thus a higher number of active flows. This in turn results in a longer duration of interference on surrounding base stations, causing a strong correlation between the activity states of the base stations. Such a system can be modelled as a network of multi-class processor-sharing queues, where the service rates for the various classes at each queue vary over time as governed by the activity state of the other queues. The complex interaction between the various queues renders an exact analysis intractable in general. A simplified network with only one class per queue reduces to a coupled-processors model, for which there are few results, even in the case of two queues. We thus derive bounds and approximations for key performance metrics like the number of active flows, transfer delays, and flow throughputs in the various cells. Importantly, these bounds and approximations are insensitive, yielding simple expressions, that render the detailed statistical characteristics of the system largely irrelevant.
CapProbe
Authors: Kapoor Rohit , Chen Ling-Jyh , Nandan Alok , Gerla Mario , Sanadidi M. Y.
Published: January 2007

The problem of estimating the capacity of an Internet path is one of fundamental importance. Due to the multitude of potential applications, a large number of solutions have been proposed and evaluated. The proposed solutions so far have been successful in partially addressing the problem, but have suffered from being slow, obtrusive or inaccurate. In this work, we evaluate CapProbe, a low-cost and accurate end-to-end capacity estimation scheme that relies on packet dispersion techniques as well as end-to-end delays. The key observation that enabled the development of CapProbe is that both compression and expansion of packet pair dispersion are the result of queuing due to cross-traffic. By filtering out queuing effects from packet pair samples, CapProbe is able to estimate capacity accurately in most environments, with minimal processing and probing traffic overhead. In fact, the storage and processing requirements of CapProbe are orders of magnitude smaller than most of the previously proposed schemes. We tested CapProbe through simulation, Internet, Internet2 and wireless experiments. We found that CapProbe error percentage in capacity estimation was within 10% in almost all cases, and within 5% in most cases.
Combining routing and traffic data for detection of IP forwarding anomalies
Authors: Roughan Matthew , Griffin Tim , Mao Morley , Greenberg Albert , Freeman Brian
Published: January 2007

IP forwarding anomalies, triggered by equipment failures, implementation bugs, or configuration errors, can significantly disrupt and degrade network service. Robust and reliable detection of such anomalies is essential to rapid problem diagnosis, problem mitigation, and repair. We propose a simple, robust method that integrates routing and traffic data streams to reliably detect forwarding anomalies. The overall method is scalable, automated and self-training. We find this technique effectively identifies forwarding anomalies, while avoiding the high false alarms rate that would otherwise result if either stream were used unilaterally.
Quantifying trade-offs in resource allocation for VPNs
Authors: Raghunath Satish , Kalyanaraman Shivkumar , Ramakrishnan K. K.
Published: January 2007

Virtual Private Networks (VPNs) feature notable characteristics in structure and traffic patterns that allow for efficient resource allocation. A strategy that exploits the underlying characteristics of a VPN can result in significant capacity savings to the service provider.There are a number of admission control and bandwidth provisioning strategies to choose from. We examine trade-offs in design choices in the context of distinctive characteristics of VPNs. We examine the value of signaling-based mechanisms, traffic matrix information and structural characteristics of VPNs in the way they impact resource utilization and service quality. We arrive at important conclusions which could have an impact on the way VPNs are architected. We show that the structure of VPNs profoundly influences achievable resource utilization gains with various admission control and provisioning schemes.
Assessing the quality of hypertext views
Authors: Bruza P. D. , van der Weide Th. P.
Published: January 2007

In this article the problem of assessing the quality of hypertext views is considered. This is done in terms of a formal model of hypertext in which the view is a central aspect. The objects in a view are described in terms of so called index expressions which are a powerful object characterization mechanism. These characterizations are manipulated by a calculus, which allows quantification of notions such as cohesion and relevance. These latter are useful criteria for judging the quality of a view.
Performance measurement in a fuzzy retrieval environment
Authors: Buell Duncan A. , Kraft Donald H.
Published: January 2007

We shall consider retrieval performance measures for generalized (non-Boolean) queries and indexing functions. The meanings of recall and precision in such a generalized system will be discussed. Finally, we shall explore the meaning and difficulty of using such measures to compare Boolean and non-Boolean retrieval systems.
On the limitations of document ranking algorithms in information retrieval
Authors: Stirling Keith H.
Published: January 2007

A document retrieval system should rank documents in order of their usefulness or satisfaction to the users. This principle was first explicated in the classic paper by Maron and Kuhns (1). Additional considerations concerning document ranking have been suggested by other researchers (2,3). Particular attention will be given here to the ranking algorithm appropriate for those presenting the same request, but having different information needs. The research on which this report is based identifies limitations associated with sequencing rules that use a probability ranking technique (4). Three basic and somewhat interdependent limitations will be discussed.
Content analysis as a word-processing option
Authors: Carroll John M.
Published: January 2007

A simple content-analysis program incorporated in a word-processing system can display the most significant sentence of a page of text and give a short list of the more important words. This could help authors write titles, summaries, and descriptor lists. The content-analysis program relies on word frequency, precedence, and co-occurrence as indicators of content significance. Test show it performs at least as well as some trained indexers.
A study of the overlap among document representations
Authors: Katzer Jeffrey , Tessier Judith , Frakes William , Das-Gupta Padmini
Published: January 2007

Most previous investigations comparing the performance of different representations have used recall and precision as performance measures. However, there is evidence to show that these measures are insensitive to an important difference between representations. To explain, two representations may perform similarly on these measures, while retrieving very different sets of documents. Equivalence of representations should be decided on the basis of similarity in performance and similarity in the documents retrieved. This study compared the performance of four representations in the PsycAbs database. In addition, overlap between retrieved sets was also computed where overlap is the proportion of retrieved documents that are the same for pairs of document representations. Results indicate that for any two representations considered, performance values differed slightly while overlap scores were also low, thus supporting the evidence that recall and precision as performance measures mask differences between the sets of retrieved documents. Results are interpreted to propose an optimal ordering of the representations and to examine the contribution of each representation given this combination.
The normalized recall and related measures
Authors: Bollmann Peter
Published: January 2007

The normalized recall is one of the most popular evaluation measures for information retrieval systems. In this paper an overview of its development is given. It is then shown that the normalized recall is closely related to other measures such as the CRE-measure and the expected search length. Some implications are analysed.
Combinatorial compression and partitioning of large dictionaries
Authors: Fraenkel Aviezri S. , Mor Moshe
Published: January 2007

A method for compressing large dictionaries is proposed, based on transforming words into lexicographically ordered strings of distinct letters, together with permutation indexes. Algorithms to generate such strings are described. Results of applying the method to the dictionaries of two databases, in Hebrew and English, are presented in detail. The main message is a method of partitioning the dictionary such that the "information bearing fraction" is stored in fast memory, and the bulk in auxiliary memory.
Derived search keys for bibliographic retrieval
Authors: Yannakoudakis E J
Published: January 2007

A principle of information science states that the entropy of a set of symbols is maximised when the probability of occurrence of each becomes the same. This paper presents the results of a number of experiments which utilise this principle to construct fixed length keys from pertinent fields in order to locate and retrieve unique records as well as clusters with lexically homogeneous information. Each key incorporates codes derived by various positional selection methods and their discriminating strength proves to be well over 95%.
An approach to enhancement of statistical survey databases
Authors: Griffiths Jose-Marie , King Donald W.
Published: January 2007

This paper deals with statistical databases that are generated from statistical surveys and that reside in organizations which perform a large number of surveys--some of which are repetitive. Examples of such organizations are Federal statistical agencies such as the Energy Information Administration, Bureau of Labor Statistics, National Center for Educational Statistics, National Center for Health Statistics, etc; state governments that have bureaus or departments that collect such data; and marketing research departments of most large consumer-oriented companies. Computer processing has provided a powerful tool for storing, manipulating, and analyzing statistical survey data. However, in addition to these advantages, computing has created a major problem in that most data analysts and users have lost touch with the data and their generation. They no longer have the feel and sense for the data that once was possible. In this paper we present an approach to database design that will directly attack this problem and enhance the usefulness of such databases as well.
Use of dynamic discrimination values in a document retrieval system
Authors: Dattola Robert T.
Published: January 2007

The use of discrimination values as a term weighting function in document retrieval systems is examined. It is shown that regular discrimination values are too costly to compute after every update to the data base. Dynamic discrimination values that are easy to update are defined for use as approximations to regular values. Experiments are performed comparing regular vs. dynamic discrimination values. Actual user queries from an operational data base are used to evaluate dynamic discrimination values in a production environment. Generalized forms of normalized recall and precision are used as evaluation measures. Retrieval results indicate statistically significant improvements using dynamic discrimination weighting.
An empirical comparison
Authors: Mazlack Lawrence J.
Published: January 2007

Unidirectional trees and lattices may both be used to hold a symbolic data base consisting of lexes, lexemes or other symbol strings. This paper empirically compares placing symbolic information into both trees and lattices (a lattice may be thought of as a unidirectional network with single and initiating and terminating nodes).
Document representation models for retrieval systems
Authors: Miller Leslie
Published: January 2007

Document retrieval system models are presented. Measures to rank the closeness of documents to a query are given. Algorithms to calculate the measures for graph and partition models are provided.
Message extraction through estimated relevance
Authors: Landauer Christopher , Mah Clinton
Published: January 2007

METER is a text analysis and retrieval system for non-expert computer users to exploit statistical associations between index terms of documents. It will run on a DEC PDP-11/45 minicomputer with continually changing collections of up to 20,000 documents at a time. A scaled version of METER with all major features of the full system has been implemented on a DEC PDP-11/70 as an experimental test bed for evaluation and comparison of associative retrieval algorithms. Although the basic structure of METER is similar to earlier statistical systems for retrospective document searches, the severe requirements of frequent updates of a document collection, of running on a small processor, and of meeting needs of users with little technical training have led to some novel developments. Among these are an update procedure that draws as much as possible on intermediate results from previous updates and a user interface that provides for control over the process of retrieval without calling for knowledge of how that process works.
Analysis of an inverted data base structure
Authors: Hill Edward
Published: January 2007

An inverted data base organization is analyzed. The inverted directory is viewed realistically as another large data base. Algorithms and formulations are derived to estimate the average number of accesses for insertion, retrieval and deletion of items from the data base. An average load time is also presented for the inverted data base.
Does relevance feedback improve document retrieval performance?
Authors: Williamson Robert E.
Published: January 2007

Many authors (1, 2, 3, 5, 6, 7) have suggested that overall performance of a document retrieval system is improved by relevance feedback. Relevance feedback denotes the last three steps in the following process: 1) the searcher enters a query, 2) the system prepares a ranked list of suggested documents, 3) the searcher judges some of the documents for relevancy, 4) the searcher informs the system of these documents judged and of the judgement, 5) the system constructs a new query based on the descriptors used in the original query and the descriptors used in the documents judged, 6) the system prepares a second ranked list of suggested documents.

The presumption is that the second list is better than the first. By all performance measures (e.g. “fluid ranking” and “frozen ranking”), the second list is better than the first. However, if one
reranks
documents in the
original
list so as to reflect the searcher's efforts (step 3), the corresponding performance measures are comparable to those for the second list. The marginal difference between the performance measures for the ”reranked original” list (searcher's efforts alone) and the second list (which includes computer efforts) makes it unclear if the cost of steps 4 through 6 above can be justified. It is hoped that advocates of relevance feedback will present “reranked original” performance measures as a basis for any performance improvement claims.

This paper also presents three reasonable, easily understood retrieval procedures for which the frozen ranking, the fluid ranking, and the reranked original evaluations are “obviously” the pertinent way to evaluate. Relevance feedback techniques as implemented in Salton's SMART DRS appear to show that it is worthwhile for user's to read abstracts prior to evaluation of full texts. The last indication presented in this paper is that the relevance feedback performance improvements noted using SMART are due mostly to the user making assessments; subsequent computer efforts appear to be most likely to result in no further change. For a query for which there is a subsequent change, the change is as likely to be harmful as helpful.
A study of interleaved memory systems by trace driven simulation
Authors: Terman Fred W.
Published: January 2007

A model of interleaved memory systems for IBM System/360 and System/370 architecture has been investigated by means of a trace driven simulation. The model used is an extension of one due to G. J. Burnett and E. G. Coffman, Jr. The trace data to drive the simulation was obtained from instruction-by-instruction traces of typical IBM 360/370 programs and of the OS/VS2 operating system. The predictions of the Burnett-Coffman model are found to fit well with the simulation results for the fetching of instructions. For the fetching of operands, however, the simulation results show only about half the increase in the memory bandwidth that the Burnett-Coffman analysis predicts. This indicates that data references on the IBM 360/370 are not random in the way assumed by Burnett and Coffman. In fact, repetitive references to the same memory location occur often enough to limit the memory bandwidth increase which can be obtained by interleaving.
I/O buffer performance in a virtual memory system
Authors: Sherman Stephen W. , Brice Richard S.
Published: January 2007

In this study we construct a simulator of a data base management system running in a virtual memory environment. We use the simulator to investigate the value of using an I/O buffer in this environment. The simulator is driven by trace data obtained with a software probe. The simulator is validated and is used to verify a theoretical model which predicts paging and disk access rates produced by use of an I/O buffer in a virtual memory environment. Results from a multi-factor set of simulation experiments are analyzed. The factors include three page replacement algorithms, four buffer management algorithms, five virtual buffer sizes, three values for real memory and six well known and widely differing distributions for creating sequences of requests to the simulated data base management system.
Minimization of supervisor conflict for multiprocessor computer systems
Authors: Raynor Randy J. , Gwynn John M.
Published: January 2007

In a multiprocessor system, the handling of interrupts generated by jobs in the processors is assigned to a supervisory program and associated data base. The two basic philosophies for deciding which processor executes the supervisor are master-slave and floating executive control. In either case, queueing of requests to the supervisor may occur. With the master-slave structure, the master processor can handle only one request at a time. With floating executive control, while any processor can execute the supervisor, only one processor at a time can be allowed to access the supervisor's data base.

A processor which is waiting to use the supervisor is not doing useful work. Therefore, queueing of requests to the supervisor causes a degradation in the performance of the system. Previous studies have indicated that this degradation is significant for systems with a large number of processors.

A methodology is developed through simulation which reduces supervisor queueing by scheduling jobs to processors such that they request the use of the supervisor when the supervisor is predicted to be available. Information concerning job execution characteristics required by the scheduler is shown to be available at sufficient accuracy via dynamic monitoring and forecasting during normal program execution.
Experience with the central server model on a lightly-loaded system
Authors: Agrawala A. K. , Larsen R. L.
Published: January 2007

Analytic models potentially provide an elegant means of estimating the performance of computer systems at a rather nominal cost. The assumptions which must be made about a system in order to construct a mathematically tractable model, however, are usually severe enough to cast doubt on the validity of the results produced by such a model. Further, relaxation of an assumption often renders an analytic technique inapplicable, such that simulation becomes the preferred approach to system modeling.

To investigate the boundary between analytic models and simulation models a computer program has been developed which provides a framework within which to develop and compare both analytic and simulation models. A general queuing network architecture has been adopted. The program is extensible with respect to analytic techniques, queuing disciplines and probability density functions.

Using this program, models of a lightly loaded batch multiprogramming system were constructed. The system was viewed as a network of servers preceded by queues. The central processing unit was one server and each I/O channel was treated as a separate server. The channels were organized in parallel with respect to each other, and in series with respect to the central processing unit. Tasks were viewed as tokens flowing through the network, being delayed by each server for queuing delays and service. Delays between task termination and initiation of a new task were modeled by additional servers operating in parallel to the I/O channel servers. An analytic solution was computed for this model for the steady state case with exponentially distributed service times and the first-come-first-served queuing discipline with unlimited capacity queues. Typical errors of 18% were observed for cpu utilization and I/O activity. The model was then modified to more realistically account for the behavior of partitions. The delay servers were modeled with unit capacity queues. This model was solved by simulation, yielding errors of 4% for cpu utilization and I/O activity.
When to stop a simulation run
Authors: Schwetman Herbert D. , Bruell Steven C.
Published: January 2007

The use of an efficient stopping rule can assist in the achievement of accurate simulation results at a reduced cost of computation. Conversely, with an inefficient stopping rule, either in-accurate results or excessive costs can occur. The problem of deciding when to stop a simulation model of a computer system is further complicated by the fact that a key parameter, response time at a service center, is not an independent random variable. In spite of this complication, procedures for determining the number of observations of response time variables required to achieve statistically valid results have been developed.

This paper presents, via the case-study approach, the effects of using an insufficient number of observations of response time and the improved accuracy which is obtained when an efficient stopping rule is used. While these results are not new, they are perhaps not widely known in the field of simulation of computer systems. We therefore view the contribution of this paper as that of demonstrating the application of such results in this field, so that other researchers can make use of them. An appendix includes a brief description of the algorithms used.
Testing of microprograms using the lockheed SUE microinstruction simulator
Authors: Davidson Scott , Tao William
Published: January 2007

Each microinstruction of a microprogram written for a horizontally microprogrammable machine can affect the machine state in quite complex ways. A microinstruction simulator that allows a microprogrammer to examine the entire processor state is a valuable tool in the testing of microcode.

The debugging aids made available by the simulator, as well as the design technique used in the construction of a microprogram, will tend to determine the strategy used in testing the microcode.

This paper describes one such simulator and a set of testing strategies found useful in working with it. The machine simulated is the Lockheed SUE, a 16 bit microprogrammable minicomputer. The SUE Simulator not only allows the display of the processor state, but allows most of the state to be modified by the user.

A testing strategy using the features of the Simulator is presented for a microprogram written using bottom-up techniques. The Simulator is also shown to be useful in testing microprograms written using other methods, and in simplifying and speeding the testing process.

Finally, the use of the Simulator in examining the effects of modifications to the processor on the microprogramming task is discussed.
Workshop session
Authors: Segal Ronald , White Norman
Published: January 2007

The management requirements and characteristics of large simulation projects will be explored during this session. Note that, as simulation technology matures, there is an increasing demand for the development of useful products within specified time and resource constraints - a requirement not unique to simulation. A great deal of recent attention, for example, has been devoted to the management of business data processing programming projects. Both classical methods for project management like PERT and CPM, and the newer methods such as chief programmer team organization and top down design, have been extremely useful in this area.

Unfortunately, simulation studies differ in many ways from the business data processing applications that have been described. As an example, it is not clear that a management approach suitable for the development of an accounts receivable system is best for the design and implementation of a large simulation model. Using the techniques now recognized as useful for other types of programming projects as a starting point, approaches and guidelines for managing large simulation projects will be discussed in this workshop.
Production and representation of computer system simulation models
Authors: Iazeolla Giuseppe G. , Martinelli Enrico , Tedone Orazio
Published: January 2007

The problem of the production of computer systems simulation models is dealt with. The software production process is generally carried out without considering the performance aspects of the whole system: performance evaluation is generally made later, once the system has been implemented. In this paper the process of the development of a system simulation model which can be used to discover aspects of system behaviour before the system is completely implemented is investigated. This process starts from the knowledge of the technical specifications of the software system and then, proceeding by levels of abstraction, yields a top-down model specification in terms of resources, resource requests, resource activities, etc.

J.D. Noe and G.J. Nutt's Evaluation Nets are used for the progressive model development. E-nets provide a formal system representation which can either be supplied to a system for the automatic generation of the simulation code, or used for the straightforward coding of the simulation program in any language.
Processor System Modeling - a language and simulation system
Authors: Pfisterer Fredrick , Purdy William C. , Lehmann Leonard
Published: January 2007

There is a need for a language and simulation system that computer systems designers (rather than programmers) can use to build and exercise models of computer systems. The major characteristics of such a language and system are presented.

A brief overview of the Processor System Modeling (PSM) system, consisting of PSM language input, translation to Simscript, execution, and interactive post processor operation on a trace of the results, is outlined.

The different types of statements in the language of the PSM system and their use are described. The major features of the language and system, which allow it to be used for constructing simple models quickly while still permitting complex systems and behavior to be simulated, are presented. Examples are used to demonstrate the use of these features, to illustrate the structure of the language, and to show its naturalness for the job of simulating computer systems.

The reasons for having a post-processor rather than statistics gathering routines are given. The two types of queries that may be made through the post-processor, about sequential events and about statistics, are described and examples given.
A microprogrammed search controller for a text scanning processor
Authors: Burkowski F. J.
Published: January 2007

The objective of the research in this paper is the design of a non-numeric processor to be used in the scanning of textual information brought in from serial storage. Source text progresses through a linear array of 32 cells each cell capable of holding one character. With all cells operating in parallel, character subsequences in the source stream can be compared with character strings in any one of 16 registers associated with the cellular array. Various modules associated with the array are used to aid the query resolution process. The overall design emphasizes speed of execution and versatility of operation.
Hardware for searching very large text databases
Authors: Haskin Roger
Published: January 2007

This paper discusses the problem of searching very large text databases. It is shown that conventional techniques for searching current databases cannot be scaled up to larger ones, and that it is necessary to build hardware to search the database in parallel if reasonable search times are expected. The part of the search process requiring the highest bandwidth is scanning the database to detect instances of search terms. Methods of doing this in hardware that have been mentioned in the literature are examined, and design criteria for term matchers are discussed. A new design that uses a nondeterministic finite state automaton to control matching, is introduced, its operation is explained, and the practicality of using it in a real system is discussed.
A proposal for a hardware text processor
Authors: Mukhopadhyay Amar
Published: January 2007

Because of the tremendous growth in the terminal-oriented users community, software text editor is increasingly becoming a significant overhead for the computing systems. The files being manipulated by text editors are usually small but undergo rapid growth and development in its short-lived life-cycle. A look into the basic command structure of these text editors reveal that the operations performed by them fundamentally consist of pattern matching, pattern transformation, pattern deletion and insertion, and management of a set of counters and pointers.

It is proposed in this paper that a specialized front-end processor with built-in string processing hardware provide a natural solution to the problem. This paper presents a possible architecture and logical capabilities of such a machine as an embellishment of microprocessors to be used for intelligent terminals. In the process, the structure of a general purpose non-numeric processor is evolved.
RELACS a Relational Associative Computer System
Authors: Oliver Ellen J. , Berra P. Bruce
Published: January 2007

Recent advances in LSI, VLSI and memory technology have led to a reduction in hardware cost and an increase in mass storage capacity such that an associative array memory can be produced and supported. Toward this end, in this paper such an associative array computer called
REL
ational
A
ssociative
C
omputer
S
ystem (RELACS) is proposed.
Towards an efficient, machine-independent language for microprogramming
Authors: Patterson David A. , Lew Karl , Tuck Richard
Published: January 2007

A machine independent low level language YALLL is presented. This language produces microcode for two very different machines: Hewlett Packard HP 300 and Digital Equipment Corporation VAX 11/780. The efficiency of this language is tested by comparing two examples on both machines to microassembly coded versions. To our best knowledge, this is the first time programs have been compiled and executed on two different microarchitectures. These examples also let us compare the efficiency of the microarchitectures and macroarchitectures of these machines and re-examine the benefits of microprogramming versus macroprogramming. We conclude this paper with comments upon transportability of high level microprogramming languages.
Application of hardware description languages to microprogramming
Authors: Drongowski Paul J. , Rose Charles W.
Published: January 2007

The use of microprogrammable processors and networks of microcomputers has induced a reconsideration of development tools and methodologies for system design and construction. This article presents the history, structure, and use of a system developed at Case Western Reserve to support the development of these kinds of systems. Other applications of hardware description languages to microprogramming and system development are discussed. The paper concludes with a discussion of limitations on the application of hardware description languages to this area as a consequence of faults in the languages themselves.
Algorithm implementation on specific microprogrammed structure
Authors: Dromard D. , Dromard F.
Published: January 2007

We currently see many works which have been done in the microprogramming field, to facilitate and to improve algorithm implementations on existing microprogrammable structures. Very few of them were executed with a top down approach, though it seems to be an attractive possibility to implement algorithms on dedicated structures. In addition, the top down approach becomes now realistic with the advent of very large scale integration, and offers fruitful perspectives. In our paper, we describe a method using automata representations, permitting an efficient algorithm implementation on specific microprogrammed structures. An example is described to illustrate the method possibilities altogether.
An implementation of microdiagnostics on the ECLIPSE® MV/8000
Authors: Reilly Paul , Shanahan Elizabeth , Staudaher Steven
Published: January 2007

The effectiveness of using a microcoded Independent Diagnostic Instruction Set for the development, manufacturing and field support of the 32-bit ECLIPSE® MV/8000 data processing system is demonstrated. A separate Diagnostic Processor with a simple operating system and microcode debugging facility is used to aid in this task.
Performance evaluation and improvement of a dynamically microprogrammable computer with low-level parallelism
Authors: Tomita Shinji , Shibayama Kiyoshi , Kitamura Toshiaki , Hagiwara Hiroshi
Published: January 2007

A new microprogrammable computer with low-level parallelism was built and has been utilized as a research vehicle for solving different classes of research-oriented applications such as real-time processings on static/dynamic images, pictures and signals, and emulations of both existing and virtual machines including high (intermediate) level language machines.

The design goal of a research-oriented computer, QA-1, was to achieve a high degree of processing power and system flexibility by means of a low-level parallel processing organization combined with dynamically microprogrammable control. This paper describes the QA-1's architecture-tailorability to different classes of emulations for existing machines such as the PDP-11/40 and the HITAC-10, and for high-level language machines such as, BASIC and PASCAL machines. All the results obtained from these experiments, together with the ones from well-defined applications such as a real-time color animation presented in another paper, have clarified some drawbacks of the QA-1 in its architectural uniformity, high functionality and microprogram productivity. On the basis of these final evaluations of the QA-1, this paper proposes a new architecture for a next generation computer, QA-2.
The ECLIPSE® MV/8000 Microsequencer
Authors: Epstein David I.
Published: January 2007

The MV/8000 Microsequencing subsection is presented as a case study of a microprogrammed CPU engine. A brief, but comprehensive, description of the micro-orders are discussed with both hardware and firmware aspects considered. Features that are highlighted include: Micro-interruptability (a micro-trapping mechanism); True microsubroutining of macroinstructions (IPOP); Micro-dispatching capability; and test and toggle micro-controllable flags.
Design of a microcode link editor
Authors: Meyers W. J.
Published: January 2007

We developed a microcode link editor (microbinder) that supports a variety of different micromachines. The microbinder resolves symbolic label references within and between separately assembled microcode modules, allocates space for each module in control store, and constructs the control store load image and supporting tables. The microbinder also provides a number of other services called for by the special nature of micromachines. It supports microprogramming conventions at a low level to prevent misuse of the hardware, at an intermediate level to limit microfunctionality in certain environments, and at a high level to improve microcode maintainability. Details of these conventions can be defined by the user, in a symbolic language coordinated with engineering documentation. The microbinder was implemented in a high level language, which contributed to its timely delivery, flexibility, and dependability.
IBM 4341 hardware/microcode trade-off decisions
Authors: Kleinsteiber James R.
Published: January 2007

The design of IBM's 4341 Processor, as with other processors, involved many cost/performance tradeoffs. The designer is continually under pressure to increase processor speed without increasing cost or to decrease processor cost without decreasing performance.

This paper will examine some of the engineering decisions that were made in the attempt to make the 4341 a high-performing yet low cost processor. These decisions include searching for, or developing, algorithms that make the best use of hardware properties, such as data path width, arithmetic/logical operations and special functions. Functions were sought such that a small amount of added hardware would go a long way towards improving system performance. Hardware designers, microcoders and performance analysis people worked together to implement instructions, functions and algorithms with the proper mixture of hardware functions and microcode in order to build a viable processor.

Some specific functions will be covered to examine a few of the decisions. The TEST UNDER MASK performance problem will be discussed with its resulting implementation decision. The method of using EXCLUSIVE OR to clear storage and the resulting algorithm design will be shown. Other topics to be discussed include multiple hardware functions and the resulting effect on floating point, fixed point and decimal multiply; the divide function and its effect on floating point and fixed point divide; and the effect of an 8-byte data path for decimal arithmetic.
Hardware microcontrol schemes using PLAs
Authors: Papachristou Christos A.
Published: January 2007

Four new schemes for microprogram control design with programmable logic arrays (PLAs) are proposed. The general structure of the first three schemes consists of three units namely, the microcode memory (ROM), the microsequencer PLA, and a register-counter. The basic idea is to store only branching information, by means of control constructs or transactions, in the PLA(s). These transactions have simple jump-type or continue-type formats with only the jump being embedded in PLA(s).

A more general structure, scheme 4, is also proposed with the objective to generate powerful transactions implementing complex control constructs, such as microsubroutines, nested microprogram loops, etc., in addition to multiway branch capability. These transactions contain horizontally formatted directive bits and, hence, they exhibit a measure of parrallelism. The aim is to transform the sequencing structure of a microprogram into a “program” composed of these transactions. However, a directive-driven processor is required to execute each transaction in order to produce the desired address.
Two implementations of the 'FLEX' machine
Authors: Kershaw John
Published: January 2007

The FLEX high-level language architecture is introduced. Two microprogrammed implementations of FLEX are described, one based on a special purpose, horizontally coded machine and the other on a general purpose emulator called GEMINI. Examples and statistics of both microprograms are given and the two implementations compared.
Adaptation and personalization of VLSI-based computer architecture
Authors: Ishikawa Chiaki , Sakamura Ken , Maekawa Mamoru
Published: January 2007

This paper discusses the important problem of the adaptation and the personalization of VLSI-based computer systems by means of microprogramming. In order to fully exploit the VLSI chip with one million transistors on it, we propose the scheme of mass-producing the general purpose devices and then specializing them to particular application needs at the instruction set processor level and at upper levels of the computer systems. Many algorithms and examples are given. We show what facilities future computer systems should possess in the course of discussion.
Toward user sharing of the microprogramming level under UNIX on the Perkin-Elmer 3220
Authors: Roskos J. Eric , Winner Robert I.
Published: January 2007

A master/slave model of writable control store is presented which is claimed to be a better representation of the operating system view of control store than models which more accurately portray the physical reality. Reported work includes the completed development of UNIX tools: an assembler generating relocatable, linkable microcode; a linking, relocating loader; a fast absolute loader; an interactive hard debugging aid allowing the setting of breakpoints; and alterations of the UNIX kernel allowing the driving of WCS as a “slave processor” consistent with the model. Code for the system driver and microcode portions of the debugger are included in the paper. The design goals of the multi-user sharing of control store, representing work now in progress, are listed. These include the use of the UNIX text segment management as the basis for association of control store routines with processes and the use of the debugging aid snapshot routines in the swapper.
The Micro8 microcode assembler
Authors: Greenberg Kenneth F.
Published: January 2007

This paper describes Micro8, a commercially-available microcode assembler written in ISO standard Pascal to enhance portability. Micro8 is designed to be a useful tool for both bit-slice and discrete logic designs. Considerable flexibility in definition of the microinstruction is provided to support both vertical and horizontal microwords. Debugging assistance is included in the form of a symbol cross reference listing, a map of control store locations, and diagnostic messages. Various features provided by the assembler are described, as are examples of typical microprogram sections.
MIDAS—microprogram description and analysis system
Authors: Hansen Igor
Published: January 2007

This paper did not arrive in time to be included in the Proceedings.
MIDL - a microinstruction description language
Authors: Sint Marleen
Published: January 2007

A microinstruction description language called MIDL is introduced. A MIDL description of a microarchitecture defines the semantics and triggering conditions of all microoperations. It also defines operand selection. MIDL incorporates a timing model that allows detailed specification of the timing of each microoperation, and a sequencing model that allows the description of many different sequencing schemes.
High-level microprogramming with APL syntax
Authors: Hobson Richard F. , Hannon Patrick , Thornburg Jonathan
Published: January 2007

The article demonstrates how higher-level microprograms can be written in APL notation. With an architecture support package (ASP) defining and emulating target machine features, the resulting 'microAPL' code is directly APL executable. Firmware development is very straightforward. An implemented ASP, microAPL compiler, and microAPL linker are discussed. MicroAPL is also compared with S* notation.
General microprogram width reduction using generator sets
Authors: Martinez-Carballido Jorge Francisco , Powers V. Michael
Published: January 2007

The problem of reducing the microinstruction length for a parallel microprogram, by trading off microprogram width (bits) for subsequent logic, is considered. In a generalization of previous methods, it is shown that a considerable reduction of microprogram storage size can be achieved by selecting a subset of the original microorders to serve as inputs to some generating logic in order to provide all the microorders in the original microprogram. Heuristic solution methods are shown, along with ways to control the bounds of the solutions, allowing the designer the choice between a fast solution and an optimal solution. Examples show the effects of using these methods, alone and in conjunction with previously published methods for width reduction. Applications of the width reduction technique to reasonable modern design situations are discussed.
Keynote address - the processor instruction set
Authors: Wilkes Maurice V.
Published: January 2007

This keynote address contains a brief account of the arguements being advanced in favor of reduced instruction sets. These arguements have relevance both to single chip computers and to larger computers. Some comments are made on instruction set design from a compiler writer's point of view, and on the advantages to be gained from regarding the design of an instruction set and the code generator of the compiler as a single task.