Exploiting Runtime Information in the IDE

Developers rely on the mechanisms provided by their IDE to browse and navigate a large software system. These mechanisms are usually based purely on a system's static source code. The static perspective, however, is not enough to understand an object-oriented program's behavior, in particular if implemented in a dynamic language. We propose to enhance IDEs with a program's runtime information (eg. message sends and type information) to support program comprehension through precise navigation and informative browsing. To precisely specify the type and amount of runtime data to gather about a system under development, dynamically and on demand, we adopt a technique known as partial behavioral reflection. We implemented navigation and browsing enhancements to an IDE that exploit this runtime information in a prototype called Hermion. We present preliminary validation of our experimental enhanced IDE by asking developers to assess its usefulness to understand an unfamiliar software system.

Abundance and biomass of in- and epibenthic invertebrate macrofauna in the German Bight from 1969 to 2000

In order to examine the long-term development of offshore macrozoobenthic soft-bottom communities of the German Bight, four representative permanent stations (MZB-SSd, -FSd, -Slt, -WB) have been sampled continuously since 1969. Inter-annual variability and possible long-term trends were analysed based on spring-time samples from 1969 until 2000. This is part of the ecological long-term series of the AWI and is supplemented by periodic large-scale mapping of the benthos. The main factors influencing the development of the benthic communities are biological interactions, climate, food supply (eutrophication) and the disturbance regime. The most frequent disturbances are sediment relocations during strong storms or by bottom trawling, while occasional oxygen deficiencies and extremely cold winters are important disturbance events working on a much larger scale. Benthic communities at the sampling stations show a large inter-annual variability combined with a variation on a roughly decadal scale. In accordance with large-scale system shifts reported for the North Sea, benthic community transitions occurred between roughly the 1970ies, 80ies and 90ies. The transitions between periods are not distinctly marked by strong changes but rather reflected in gradual changes of the species composition and dominance structure.

Perfect imaging of three object points with only two analytic lens surfaces in two dimensions

In this work, a new two-dimensional analytic optics design method is presented that enables the coupling of three ray sets with two lens profiles. This method is particularly promising for optical systems designed for wide field of view and with clearly separated optical surfaces. However, this coupling can only be achieved if different ray sets will use different portions of the second lens profile. Based on a very basic example of a single thick lens, the Simultaneous Multiple Surfaces design method in two dimensions (SMS2D) will help to provide a better understanding of the practical implications on the design process by an increased lens thickness and a wider field of view. Fermat?s principle is used to deduce a set of functional differential equations fully describing the entire optical system. The transformation of these functional differential equations into an algebraic linear system of equations allows the successive calculation of the Taylor series coefficients up to an arbitrary order. The evaluation of the solution space reveals the wide range of possible lens configurations covered by this analytic design method. Ray tracing analysis for calculated 20th order Taylor polynomials demonstrate excellent performance and the versatility of this new analytical optics design concept.

Combining a Similar Coefficient Identification Algorithm with the Boundary Element Method

The boundary element method (BEM) has been applied successfully to many engineering problems during the last decades. Compared with domain type methods like the finite element method (FEM) or the finite difference method (FDM) the BEM can handle problems where the medium extends to infinity much easier than domain type methods as there is no need to develop special boundary conditions (quiet or absorbing boundaries) or infinite elements at the boundaries introduced to limit the domain studied. The determination of the dynamic stiffness of arbitrarily shaped footings is just one of these fields where the BEM has been the method of choice, especially in the 1980s. With the continuous development of computer technology and the available hardware equipment the size of the problems under study grew and, as the flop count for solving the resulting linear system of equations grows with the third power of the number of equations, there was a need for the development of iterative methods with better performance. In [1] the GMRES algorithm was presented which is now widely used for implementations of the collocation BEM. While the FEM results in sparsely populated coefficient matrices, the BEM leads, in general, to fully or densely populated ones, depending on the number of subregions, posing a serious memory problem even for todays computers. If the geometry of the problem permits the surface of the domain to be meshed with equally shaped elements a lot of the resulting coefficients will be calculated and stored repeatedly. The present paper shows how these unnecessary operations can be avoided reducing the calculation time as well as the storage requirement. To this end a similar coefficient identification algorithm (SCIA), has been developed and implemented in a program written in Fortran 90. The vertical dynamic stiffness of a single pile in layered soil has been chosen to test the performance of the implementation. The results obtained with the 3-d model may be compared with those obtained with an axisymmetric formulation which are considered to be the reference values as the mesh quality is much better. The entire 3D model comprises more than 35000 dofs being a soil region with 21168 dofs the biggest single region. Note that the memory necessary to store all coefficients of this single region is about 6.8 GB, an amount which is usually not available with personal computers. In the problem under study the interface zone between the two adjacent soil regions as well as the surface of the top layer may be meshed with equally sized elements. In this case the application of the SCIA leads to an important reduction in memory requirements. The maximum memory used during the calculation has been reduced to 1.2 GB. The application of the SCIA thus permits problems to be solved on personal computers which otherwise would require much more powerful hardware.

Avaliação de incertezas na calibração automática do modelo SWMM

Este trabalho é referente ao desenvolvimento de um calibrador multiobjetivo automático do modelo SWMM (Storm Water Management Model), e avaliação de algumas fontes de incertezas presentes no processo de calibração, visando à representação satisfatória da transformação chuva-vazão. O código foi escrito em linguagem C, e aplica os conceitos do método de otimização multiobjetivo NSGAII (Non Dominated Sorting Genetic Algorithm) com elitismo controlado, além de utilizar o código fonte do modelo SWMM para a determinação das vazões simuladas. Paralelamente, também foi criada uma interface visual, para melhorar a facilidade de utilização do calibrador. Os testes do calibrador foram aplicados a três sistemas diferentes: um sistema hipotético disponibilizado no pacote de instalação do SWMM; um sistema real de pequenas dimensões, denominado La Terraza, localizado no município de Sierra Vista, Arizona (EUA); e um sistema de maiores dimensões, a bacia hidrográfica do Córrego do Gregório, localizada no município de São Carlos (SP). Os resultados indicam que o calibrador construído apresenta, em geral, eficiência satisfatória, porém é bastante dependente da qualidade dos dados observados em campo e dos parâmetros de entrada escolhidos pelo usuário. Foi demonstrada a importância da escolha dos eventos utilizados na calibração, do estabelecimento de limites adequados nos valores das variáveis de decisão, da escolha das funções objetivo e, principalmente, da qualidade e representatividade dos dados de monitoramento pluvio e fluviométrico. Conclui-se que estes testes desenvolvidos contribuem para o entendimento mais aprofundado dos processos envolvidos na modelagem e calibração, possibilitando avanços na confiabilidade dos resultados da modelagem.

Método multigrid algébrico: reutilização das estruturas multigrid no transporte de contaminantes

A necessidade de obter solução de grandes sistemas lineares resultantes de processos de discretização de equações diferenciais parciais provenientes da modelagem de diferentes fenômenos físicos conduz à busca de técnicas numéricas escaláveis. Métodos multigrid são classificados como algoritmos escaláveis.Um estimador de erros deve estar associado à solução numérica do problema discreto de modo a propiciar a adequada avaliação da solução obtida pelo processo de aproximação. Nesse contexto, a presente tese caracteriza-se pela proposta de reutilização das estruturas matriciais hierárquicas de operadores de transferência e restrição dos métodos multigrid algébricos para acelerar o tempo de solução dos sistemas lineares associados à equação do transporte de contaminantes em meio poroso saturado. Adicionalmente, caracteriza-se pela implementação das estimativas residuais para os problemas que envolvem dados constantes ou não constantes, os regimes de pequena ou grande advecção e pela proposta de utilização das estimativas residuais associadas ao termo de fonte e à condição inicial para construir procedimentos adaptativos para os dados do problema. O desenvolvimento dos códigos do método de elementos finitos, do estimador residual e dos procedimentos adaptativos foram baseados no projeto FEniCS, utilizando a linguagem de programação PYTHONR e desenvolvidos na plataforma Eclipse. A implementação dos métodos multigrid algébricos com reutilização considera a biblioteca PyAMG. Baseado na reutilização das estruturas hierárquicas, os métodos multigrid com reutilização com parâmetro fixo e automática são propostos, e esses conceitos são estendidos para os métodos iterativos não-estacionários tais como GMRES e BICGSTAB. Os resultados numéricos mostraram que o estimador residual captura o comportamento do erro real da solução numérica, e fornece algoritmos adaptativos para os dados cuja malha retornada produz uma solução numérica similar à uma malha uniforme com mais elementos. Adicionalmente, os métodos com reutilização são mais rápidos que os métodos que não empregam o processo de reutilização de estruturas. Além disso, a eficiência dos métodos com reutilização também pode ser observada na solução do problema auxiliar, o qual é necessário para obtenção das estimativas residuais para o regime de grande advecção. Esses resultados englobam tanto os métodos multigrid algébricos do tipo SA quanto os métodos pré-condicionados por métodos multigrid algébrico SA, e envolvem o transporte de contaminantes em regime de pequena e grande advecção, malhas estruturadas e não estruturadas, problemas bidimensionais, problemas tridimensionais e domínios com diferentes escalas.

An Empirical Comparison of Reuse in Embedded and Nonembedded Systems

High-quality software, delivered on time and budget, constitutes a critical part of most products and services in modern society. Our government has invested billions of dollars to develop software assets, often to redevelop the same capability many times. Recognizing the waste involved in redeveloping these assets, in 1992 the Department of Defense issued the Software Reuse Initiative. The vision of the Software Reuse Initiative was "To drive the DoD software community from its current "re-invent the software" cycle to a process-driven, domain-specific, architecture-centric, library-based way of constructing software.'' Twenty years after issuing this initiative, there is evidence of this vision beginning to be realized in nonembedded systems. However, virtually every large embedded system undertaken has incurred large cost and schedule overruns. Investigations into the root cause of these overruns implicates reuse. Why are we seeing improvements in the outcomes of these large scale nonembedded systems and worse outcomes in embedded systems? This question is the foundation for this research. The experiences of the Aerospace industry have led to a number of questions about reuse and how the industry is employing reuse in embedded systems. For example, does reuse in embedded systems yield the same outcomes as in nonembedded systems? Are the outcomes positive? If the outcomes are different, it may indicate that embedded systems should not use data from nonembedded systems for estimation. Are embedded systems using the same development approaches as nonembedded systems? Does the development approach make a difference? If embedded systems develop software differently from nonembedded systems, it may mean that the same processes do not apply to both types of systems. What about the reuse of different artifacts? Perhaps there are certain artifacts that, when reused, contribute more or are more difficult to use in embedded systems. Finally, what are the success factors and obstacles to reuse? Are they the same in embedded systems as in nonembedded systems? The research in this dissertation is comprised of a series of empirical studies using professionals in the aerospace and defense industry as its subjects. The main focus has been to investigate the reuse practices of embedded systems professionals and nonembedded systems professionals and compare the methods and artifacts used against the outcomes. The research has followed a combined qualitative and quantitative design approach. The qualitative data were collected by surveying software and systems engineers, interviewing senior developers, and reading numerous documents and other studies. Quantitative data were derived from converting survey and interview respondents' answers into coding that could be counted and measured. From the search of existing empirical literature, we learned that reuse in embedded systems are in fact significantly different from nonembedded systems, particularly in effort in model based development approach and quality where the development approach was not specified. The questionnaire showed differences in the development approach used in embedded projects from nonembedded projects, in particular, embedded systems were significantly more likely to use a heritage/legacy development approach. There was also a difference in the artifacts used, with embedded systems more likely to reuse hardware, test products, and test clusters. Nearly all the projects reported using code, but the questionnaire showed that the reuse of code brought mixed results. One of the differences expressed by the respondents to the questionnaire was the difficulty in reuse of code for embedded systems when the platform changed. The semistructured interviews were performed to tell us why the phenomena in the review of literature and the questionnaire were observed. We asked respected industry professionals, such as senior fellows, fellows and distinguished members of technical staff, about their experiences with reuse. We learned that many embedded systems used heritage/legacy development approaches because their systems had been around for many years, before models and modeling tools became available. We learned that reuse of code is beneficial primarily when the code does not require modification, but, especially in embedded systems, once it has to be changed, reuse of code yields few benefits. Finally, while platform independence is a goal for many in nonembedded systems, it is certainly not a goal for the embedded systems professionals and in many cases it is a detriment. However, both embedded and nonembedded systems professionals endorsed the idea of platform standardization. Finally, we conclude that while reuse in embedded systems and nonembedded systems is different today, they are converging. As heritage embedded systems are phased out, models become more robust and platforms are standardized, reuse in embedded systems will become more like nonembedded systems.

Sequential and parallel synchronous alternating iterative methods

The so-called parallel multisplitting nonstationary iterative Model A was introduced by Bru, Elsner, and Neumann [Linear Algebra and its Applications 103:175-192 (1988)] for solving a nonsingular linear system Ax = b using a weak nonnegative multisplitting of the first type. In this paper new results are introduced when A is a monotone matrix using a weak nonnegative multisplitting of the second type and when A is a symmetric positive definite matrix using a P -regular multisplitting. Also, nonstationary alternating iterative methods are studied. Finally, combining Model A and alternating iterative methods, two new models of parallel multisplitting nonstationary iterations are introduced. When matrix A is monotone and the multisplittings are weak nonnegative of the first or of the second type, both models lead to convergent schemes. Also, when matrix A is symmetric positive definite and the multisplittings are P -regular, the schemes are also convergent.

A Finite Element Numerical Algorithm for Modelling and Data Fitting in Complex Systems

Numerical modelling methodologies are important by their application to engineering and scientific problems, because there are processes where analytical mathematical expressions cannot be obtained to model them. When the only available information is a set of experimental values for the variables that determine the state of the system, the modelling problem is equivalent to determining the hyper-surface that best fits the data. This paper presents a methodology based on the Galerkin formulation of the finite elements method to obtain representations of relationships that are defined a priori, between a set of variables: y = z(x1, x2,...., xd). These representations are generated from the values of the variables in the experimental data. The approximation, piecewise, is an element of a Sobolev space and has derivatives defined in a general sense into this space. The using of this approach results in the need of inverting a linear system with a structure that allows a fast solver algorithm. The algorithm can be used in a variety of fields, being a multidisciplinary tool. The validity of the methodology is studied considering two real applications: a problem in hydrodynamics and a problem of engineering related to fluids, heat and transport in an energy generation plant. Also a test of the predictive capacity of the methodology is performed using a cross-validation method.

Towards pattern-based design recovery

A method and a corresponding tool is described which assist design recovery and program understanding by recognising instances of design patterns semi-automatically. The approach taken is specifically designed to overcome the existing scalability problems caused by many design and implementation variants of design pattern instances. Our approach is based on a new recognition algorithm which works incrementally rather than trying to analyse a possibly large software system in one pass without any human intervention. The new algorithm exploits domain and context knowledge given by a reverse engineer and by a special underlying data structure, namely a special form of an annotated abstract syntax graph. A comparative and quantitative evaluation of applying the approach to the Java AWT and JGL libraries is also given.

Evaluation and measurement of multiprocessor systems with shared memory

This study is concerned with several proposals concerning multiprocessor systems and with the various possible methods of evaluating such proposals. After a discussion of the advantages and disadvantages of several performance evaluation tools, the author decides that simulation is the only tool powerful enough to develop a model which would be of practical use, in the design, comparison and extension of systems. The main aims of the simulation package developed as part of this study are cost effectiveness, ease of use and generality. The methodology on which the simulation package is based is described in detail. The fundamental principles are that model design should reflect actual systems design, that measuring procedures should be carried out alongside design that models should be well documented and easily adaptable and that models should be dynamic. The simulation package itself is modular, and in this way reflects current design trends. This approach also aids documentation and ensures that the model is easily adaptable. It contains a skeleton structure and a library of segments which can be added to or directly swapped with segments of the skeleton structure, to form a model which fits a user's requirements. The study also contains the results of some experimental work carried out using the model, the first part of which tests• the model's capabilities by simulating a large operating system, the ICL George 3 system; the second part deals with general questions and some of the many proposals concerning multiprocessor systems.

Bandwidth management of WiMAX systems and performance modeling

WiMAX has been introduced as a competitive alternative for metropolitan broadband wireless access technologies. It is connection oriented and it can provide very high data rates, large service coverage, and flexible quality of services (QoS). Due to the large number of connections and flexible QoS supported by WiMAX, the uplink access in WiMAX networks is very challenging since the medium access control (MAC) protocol must efficiently manage the bandwidth and related channel allocations. In this paper, we propose and investigate a cost-effective WiMAX bandwidth management scheme, named the WiMAX partial sharing scheme (WPSS), in order to provide good QoS while achieving better bandwidth utilization and network throughput. The proposed bandwidth management scheme is compared with a simple but inefficient scheme, named the WiMAX complete sharing scheme (WCPS). A maximum entropy (ME) based analytical model (MEAM) is proposed for the performance evaluation of the two bandwidth management schemes. The reason for using MEAM for the performance evaluation is that MEAM can efficiently model a large-scale system in which the number of stations or connections is generally very high, while the traditional simulation and analytical (e.g., Markov models) approaches cannot perform well due to the high computation complexity. We model the bandwidth management scheme as a queuing network model (QNM) that consists of interacting multiclass queues for different service classes. Closed form expressions for the state and blocking probability distributions are derived for those schemes. Simulation results verify the MEAM numerical results and show that WPSS can significantly improve the network's performance compared to WCPS.

Evolutionary market agents for resource allocation in decentralised systems

We introduce self-interested evolutionary market agents, which act on behalf of service providers in a large decentralised system, to adaptively price their resources over time. Our agents competitively co-evolve in the live market, driving it towards the Bertrand equilibrium, the non-cooperative Nash equilibrium, at which all sellers charge their reserve price and share the market equally. We demonstrate that this outcome results in even load-balancing between the service providers. Our contribution in this paper is twofold; the use of on-line competitive co-evolution of self-interested service providers to drive a decentralised market towards equilibrium, and a demonstration that load-balancing behaviour emerges under the assumptions we describe. Unlike previous studies on this topic, all our agents are entirely self-interested; no cooperation is assumed. This makes our problem a non-trivial and more realistic one.

Examples Illustrating some Aspects of the Weak Deligne-Simpson Problem

Research partially supported by INTAS grant 97-1644

Improved Cryptoanalysis of the Self-shrinking P-adic Cryptographic Generator

The Self-shrinking p-adic cryptographic generator (SSPCG) is a fast software stream cipher. Improved cryptoanalysis of the SSPCG is introduced. This cryptoanalysis makes more precise the length of the period of the generator. The linear complexity and the cryptography resistance against most recently used attacks are invesigated. Then we discuss how such attacks can be avoided. The results show that the sequence generated by a SSPCG has a large period, large linear complexity and is stable against the cryptographic attacks. This gives the reason to consider the SSPSG as suitable for critical cryptographic applications in stream cipher encryption algorithms.