Refereed papers

[1] Francisco José da Silva e Silva, Fabio Kon, Alfredo Goldman, Marcelo Finger, Raphael Y. de Camargo, Fernando Castor Filho, and Fábio M. Costa. Application execution management on the InteGrade opportunistic grid middleware. Journal of Parallel and Distributed Computing, 70(5):573-583, 2010. [ bib | pdf | html ]
The InteGrade project is a multi-university effort to build a novel grid computing middleware based on the opportunistic use of resources belonging to user workstations. The InteGrade middleware currently enables the execution of sequential, bag-of-tasks, and parallel applications that follow the BSP or the MPI programming models. This article presents the lessons learned over the last five years of the InteGrade development and describes the solutions achieved concerning the support for robust application execution. The contributions cover the related fields of application scheduling, execution management, and fault tolerance. We present our solutions, describing their implementation principles and evaluation through the analysis of several experimental results.

Keywords: Grid computing, Opportunistic grid, Resource management, Fault tolerance
[2] Afonso Ferreira, Alfredo Goldman, and Julian Monteiro. Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs. Wireless Networks, 16:627-640, 2010. [ bib | pdf | html ]
The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks' dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model - the evolving graphs - was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

Keywords: Ad hoc wireless networks, Sensor networks, Evolving graphs, Routing protocols, Delay tolerant networks, Performance analysis
[3] R. Y. de Camargo, A. Goldchleger, F. Kon, and A. Goldman. Checkpointing BSP parallel applications on the InteGrade Grid middleware. Concurrency and Computation: Practice and Experience, 18:567-579, 2006. [ bib | pdf | html ]
InteGrade is a Grid middleware infrastructure that enables the use of idle computing power from user workstations. One of its goals is to support the execution of long-running parallel applications that present a considerable amount of communication among application nodes. However, in an environment composed of shared user workstations spread across many different LANs, machines may fail, become inaccessible, or may switch from idle to busy very rapidly, compromising the execution of the parallel application in some of its nodes. Thus, to provide some mechanism for fault tolerance becomes a major requirement for such a system. In this paper, we describe the support for checkpoint-based rollback recovery of Bulk Synchronous Parallel applications running over the InteGrade middleware. This mechanism consists of periodically saving application state to permit the application to restart its execution from an intermediate execution point in case of failure. A precompiler automatically instruments the source code of a C/C++ application, adding code for saving and recovering application state. A failure detector monitors the application execution. In case of failure, the application is restarted from the last saved global checkpoint.

Keywords: fault tolerance, checkpointing, BSP, Grid computing
[4] Danilo Sato, Dairton Bassi, Mariana Bravo, Alfredo Goldman, and Fabio Kon. Experiences tracking agile projects: an empirical study. Journal of the Brazilian Computer Society, 12(3):45-64, 2006. [ bib | pdf | html ]
In this article, we gather results from several projects we conducted recently that use some kind of agile method. We analyze both academic and governmental software development projects, some of them using agile methods since the beginning and others in which agile methods were introduced afterwards. Our main goals are to classify the different projects, and to analyze the collected data and discover which metrics are best suited to support tracking an agile project. We use both quantitative and qualitative methods, obtaining data from the source code, from the code repository, and from the feedback received from surveys and interviews held with the team members. We use various kinds of metrics such as lines of code, number of tests, cyclomatic complexity, number of commits, as well as combinations of these. In this article, we describe in detail the projects, the metrics, the obtained results, and their analysis from our main goals standpoint, providing guidelines for the use of metrics to track an agile software development project.

Keywords: Agile Methods, Extreme Programming, Software Engineering, Tracking
[5] Alfredo Goldman, Joseph G. Peters, and Denis Trystram. Exchanging messages of different sizes. Journal of Parallel and Distributed Computing, 66(1):1-18, 2006. [ bib | pdf | html ]
This paper deals with the study of the exchange of messages among a set of processors linked through an interconnection network. We focus on general, non-uniform versions of message exchange problems in asynchronous systems with a linear cost model and messages of arbitrary sizes. We extend previous complexity results to show that the general asynchronous problems are NP-complete. We present several heuristics and determine which algorithms are best suited to several parallel systems. We propose new algorithms that combine the advantages of some of the heuristics. We conclude with experiments and simulations of the algorithms and analyses of their performances.

Keywords: Personalized communications, BSP model, Communication primitives
[6] Alfredo Goldman and Carlos Queiroz. A model for parallel job scheduling on dynamical computer Grids. Concurrency and Computation: Practice and Experience, 16:461-468, 2004. [ bib | pdf | html ]
This work presents a model that allows the execution of parallel applications in a Grid environment. Our main focus is on how to share the idle cycles of clusters and computers to execute real parallel applications. We present a new model which introduces the notions of locality and adaptability. The locality is used for job allocation, and for job migration. The adaptability provides a simple mechanism to allow clusters to join or leave a Grid. We also propose the middleware architecture to implement the model, and provide some simulation results to show the main characteristics of the model.

Keywords: Grid computing, multi-site execution, scheduling of parallel applications
[7] Andrei Goldchleger, Fabio Kon, Alfredo Goldman, Marcelo Finger, and G. C. Bezerra. InteGrade: object-oriented Grid middleware leveraging the idle computing power of desktop machines. Concurrency and Computation: Practice and Experience, 16:449-459, 2004. [ bib | pdf | html ]
Grid computing technology improves the computing experiences at organizations by effectively integrating distributed computing resources. However, just a small fraction of currently available Grid infrastructures focuses on reutilization of existing commodity computing resources. This paper introduces InteGrade, a novel object-oriented middleware Grid infrastructure that focuses on leveraging the idle computing power of shared desktop machines. Its features include support for a wide range of parallel applications and mechanisms to assure that the owners of shared resources do not perceive any loss in the quality of service. A prototype implementation is under construction and the current version is available for download.

Keywords: Grid computing, multi-site execution, scheduling of parallel applications
[8] Alfredo Goldman, Fabio Kon, Paulo J. S. Silva, and Joseph W. Yoder. Being Extreme in the Classroom: experiences Teaching XP. Journal of the Brazilian Computer Society, 10:5-21, 2004. [ bib | pdf | html ]
Agile Methods propose a new way of looking at software development that questions many of the beliefs of conventional Software Engineering. Agile methods such as Extreme Programming (XP) have been very effective in producing highquality software in realworld projects with strict time constraints. Nevertheless, most university courses and industrial training programs are still based on oldstyle heavy-weight methods. This article, based on our experiences teaching XP in academic and industrial environments, presents effective ways of teaching students and professionals on how to develop high-quality software following the principles of agile software development. We also discuss related work in the area, describe realworld cases, and discuss open problems not yet resolved.

Keywords:
[9] Alfredo Goldman, Gregory Mounie, and Denis Trystram. 1-optimality of static BSP computations: scheduling independent chains as a case study. Theoretical Computer Science, 290(3):1331-1359, 2003. [ bib | pdf | html ]
The aim of this work is to study a specific scheduling problem under the machine-independent model BSP. The problem of scheduling a set of independent chains in this context is shown to be a difficult optimization problem, but it can be easily approximated in practice. Efficient heuristics taking into account communications are proposed and analyzed in this paper. We particularly focus on the influence of synchronization between consecutive supersteps. A family of algorithms is proposed with the best possible load-balancing. Then, a strategy for determining a good compromise between the two opposite criteria of minimizing the number of supersteps and a good balance of the load is derived. Finally, a heuristic which considers the influence of the latency is presented. Simulations of a large number of instances have been carried out to complement the theoretical worst case analysis. They confirm the very good behavior of the algorithms on the average cases.

Keywords: Scheduling, Synchronization, Chains, BSP
[10] Alfredo Goldman and Denis Trystram. An efficient parallel algorithm for solving the Knapsack problem on hypercubes. Journal of Parallel and Distributed Computing, 64(11):1213-1222, 2002. [ bib | pdf | html ]
We present in this paper an efficient algorithm for solving the integral Knapsack problem on hypercube. The main idea is to represent the computations of the dynamic programming formulation as a precedence graph (which has the structure of an irregular mesh). Then, we propose a time optimal scheduling algorithm for computing the irregular meshes on hypercube.

Keywords: Hypercube, Knapsack problem, Irregular mesh, Scheduling
[11] Alfredo Goldman, A. Ferreira, and S.W. Song. Broadcasting in bus interconnection networks. Journal of Interconnection Networks, 1(2):73-94, 2000. [ bib | pdf | html ]
In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point interconnection network, usually modeled by a graph where processors are nodes and communication links are edges. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems so as to improve the communication efficiency. In this paper we study parallel architectures where the communication means are constituted solely by buses. These architectures can use the power of bus technologies, providing a way to interconnect much more processors in a simple and efficient manner. We present the hyperpath, hypergrid, hyperring, and hypertorus architectures, which are the bus-based versions of the well used point-to-point interconnection networks. Using (hyper) graph theoretic concepts to model inter-processor communication in such networks, we give optimal algorithms for broadcasting a message from one processor to all the others. For deriving high performance communication patterns we developed a new tool called simplification. The idea is to construct a graph, to be called representative graph, from the original hyper-topology, in such a way that it will become easy to describe and perform communication schemes to the former that will fit to the latter, because the simplification concept also allows us to partially use some already known communication algorithms for usual networks.

Keywords: Massively parallel architectures, multiple bus systems, global communication, communication models, hypergraphs and applications, broadcast
[12] Alfredo Goldman, A. Ferreira, and S.W. Song. Gossiping in Bus Interconnection Networks. Parallel Algorithms and Applications, 854:309-331, 1996. [ bib | pdf | html ]
Several architectures have been proposed to enhance point-to-point architectures with the addition of multiple bus systems. In particular, we consider an architecture for a massively parallel system where processors arc connected solely by buses. These architectures can use the power of bus technologies, providing a way to interconnect much more processors in a simple and efficient manner. In this paper we model the so-called bus interconnection networks (BINs) by a hypergraph. We consider the gossip operation in the various proposed architectures. We focus on the hyperpath, the d-dimensional hypergrid, the hyperring, and the d -dimensional hypertorus architectures and we give corresponding algorithms for the gossiping operation. Some lower bounds are also derived.

Keywords: Massively parallel architectures, multiple bus systems, global communication, communication models, hypergraphs and applications, gossiping, total exchange

Conference papers and posters

[1] Alfredo Goldman, Cássia G. Ferreira, Cesar G. Machado, and Paulo Floriano. Jornadas mais rápidas e compromissos em DTNs. In Anais do 28 Simposio Brasileiro de Redes de Computadores, Gramado, Brazil, 2010. [ bib | pdf ]
This article describes two algorithms to compute Fastest Journeys in Delay and Disruption Tolerant Networks in which all connections can be predicted. The first one corresponds to an algorithm already proposed, but never before implemented. The second one uses a new idea, which can be extended to compute other types of optimal journeys. Based on this new algorithm, we studied the relationship between the arrival time, the hopcount and the transit time of a journey, searching for optimal intermediate journeys that minimize two or more parameters at the same time. We present in the paper several experiments that show the importance of the proposed approach.

[2] Alfredo Goldman, Cesar G. Machado, and Paulo Floriano. Optimal Journeys and Trade-offs on DTNs. In 2nd Extreme Workshop on Communication, Dharamsalam, India, 2010. [ bib | pdf ]
This article describes algorithms to compute optimal journeys in predictable DTNs. We combine the algorithms to compute the shortest, fastest and foremost journeys in order to provide intermediate optimal journeys which can be used according to the environment characteristics. We also propose a preliminary empirical study on the number of data mules needed to provide connectivity in sparse scenarios on several environments. We present in the article several experiments that show the importance of the proposed approach.

[3] Viviane Santos and Alfredo Goldman. Aplicando Técnicas de Grounded Theory e Retrospectiva Ágil para Avaliar o Curso Laboratório XP. In Proceedings of VII Experimental Software Engineering Latin American Workshop, Goiânia, Goiás, Brazil, 2010. [ bib | pdf ]
This paper presents an empirical study about learning eXtreme Programming in an academic environment. The study employs two distinct approaches to provide triangulation of the data: qualitative analysis with grounded theory in a questionnaire and agile retrospective to investigate what to improve in the course in the students point of view. From the results, specific improvement actions were established for the next editions of the course.

[4] Luciana Arantes, Alfredo Goldman, and Pierre Sens. Towards a distributed computing model that characterizes dynamics of mobile networks. In Anais do Colóquio em Informática: Brasil/INRIA, Cooperações, Avanços e Desafios, pages 151-155, Bento Golçalves - RS, Brazil, 2009. [ bib | pdf ]
Our main goal in this proposal is to present the research possibilities opened by two previous cooperations among groups from France and Brazil in dynamic systems. Basically, we intend to add up the expertise of the French group on distributed systems with the skills of the Brazilian group on the practical use of theoretical tools in order to create a new distributed model for mobile networks (MANET). Despite the fact that both groups have conducted their researches independently, we believe that to join efforts to define such a model would be very promising and would open an interesting field of research.

[5] Rodrigo A. Dias, Alfredo Goldman, and Roberto Hirata. Middle-R - A User Level Middleware for Statistical Computing. In Anais do VII Workshop on Grid Computing and Applications, Pernambuco, Brazil, 2009. [ bib | pdf ]
In this work we present middle-R, a user-level middleware for statistical computing. It has been developed to distribute R (a language and environment for statistics) in commodity computers running Microsoft Windows. The solution is simple because it uses Alchemi, a grid middleware developed using Microsoft .NET technology in the University of Melbourne. The implemented solution uses Alchemi as a low-level middleware and makes it possible to execute R scripts in a grid environment. The solution has been successfully implemented and tested in two different environments: the didactic laboratories of a college and of a high school. The main application reported in this paper is a combinatorial task for finding molecular markers of a few genes to classify correctly samples of acute lymphoblastic leukemia against acute myeloid leukemia.

[6] Vinicius Pinheiro, Fabio Kon, and Alfredo Goldman. Towards an adaptive middleware for opportunistic environment: A Mobile Agent Approach. In MGC '09: Proceedings of the 7th International Workshop on Middleware for Grids, Clouds and e-Science, pages 1-6, Urbana Champaign, Illinois, 2009. ACM. [ bib | html ]
The mobile agent paradigm has emerged as a promising alternative to overcome the construction challenges of opportunistic grid environments. This model can be used to implement mechanisms that enable application execution progress even in the presence of failures, such as those presented by the MAG middleware (Mobile Agents for Grids). MAG includes retrying, replication, and checkpointing as fault-tolerance techniques; they operate independently from each other and are not capable of detecting changes on resource availability. In this paper, we describe a MAG extension that is capable of migrating agents when nodes fail, that optimizes application progress by keeping only the most advanced checkpoint, and that migrates slow replicas.

[7] Luciana Arantes, Alfredo Goldman, and Márcio Vinícius Dos Santos. Using Evolving Graphs to evaluate DTN routing protocols. In ExtremeCom 2009, Laônia, 2009. Proc, of the first Extreme Workshop on Communication. [ bib ]
One of the main challenges of Delay-Tolerant Networks (DTNs) is on how to define effective routing protocols. Contrarily to traditional networks, which use static routing protocols and guarantee end-to-end paths between nodes of the network, connectivity is intermittent in DTNs. A routing path between two nodes is dynamically built over the time, i.e., a connection between two intermediate nodes of a routing path is not necessarily established beforehand. Hence, it may happen that at a given time or period there is no direct path between two given nodes, however further future temporary connections between some intermediary nodes may provide a path over time, also called journey, between those two nodes. Temporary connections between nodes, denoted contacts, is thus strongly exploited by DTN routing protocols for message delivery. A DTN routing protocol must carefully select journeys between nodes for performance's sake. Usually routing takes place using a store and forward mechanism and depends on several parameters such as time of request, availability of connectivity, message size, network traffic, transmission delay, etc. Moreover, different metrics can be exploited for supporting routing decisions like the number of hops between the given nodes, the arrival.

[8] Emilio Francesquini and Alfredo Goldman. Scheduling on multi-core clusters. In Workshop on Algorithms and Techniques for Scheduling on Clusters and Grids, Les Plantiers, 2009. Proc. of ASTEC 2009. [ bib ]
Nowadays, with the advent of the multi-core technology, most of the modern computers have several cores. However, the current schedulers do not provide automatic tools to schedule tasks to the cores. Indeed, some of them consider each core as one whole node neglecting the advantages (and disadvantages) that the spatial proximity amongst the cores could provide. In this talk, we will show some of the solutions currently being employed to tackle these scheduling problems as well as propose some of our own ideas for a model which considers the multi-core context and its impact on the scheduling algorithms.

[9] M. Bougeret, P.-F. Dutot, A. Goldman, Y. Ngoko, and D. Trystram. Combining multiple heuristics on discrete resources. In Parallel Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pages 1-8, 2009. [ bib ]
In this work we study the portfolio problem which is to find a good combination of multiple heuristics to solve given instances on parallel resources in minimum time. The resources are assumed to be discrete, it is not possible to allocate a resource to more than one heuristic. Our goal is to minimize the average completion time of the set of instances, given a set of heuristics on homogeneous discrete resources. This problem has been studied in the continuous case in [T. Sayag et al., 2006]. We first show that the problem is hard and that there is no constant ratio polynomial approximation unless P = NP in the general case. Then, we design several approximation schemes for a restricted version of the problem where each heuristic must be used at least once. These results are obtained by using oracle with several guesses, leading to various tradeoff between the size of required information and the approximation ratio. Some additional results based on simulations are finally reported using a benchmark of instances on SAT solvers.

Keywords: SAT solvers, approximation ratio, constant ratio polynomial approximation, good combination, homogeneous discrete resources, multiple heuristics, parallel resources, portfolio problem, resource allocation, parallel processing, polynomial approximation, resource allocation
[10] Vinicius Pinheiro, Alfredo Goldman, and Francisco José da Silva e Silva. Agentes Móveis: Uma Abordagem para a Execução de Aplicações Longas em Ambientes Oportunistas. In VI Workshop on Grid Computing and Application, pages 109-120, Rio de Janeiro, RJ, Brazil, May 2008. [ bib | slides | pdf ]
The mobile agent paradigm has emerged as a promising alternative to overcome the construction challenges of opportunistic Grid environments. MAG (Mobile Agents for Grid Computing Environment) explores this powerful paradigm by dynamically loading grid applications into mobile agents. These MAG agents can be dynamically reallocated to Grid nodes through a transparent migration mechanism as a way to provide load balancing and support for non-dedicated nodes. MAG also includes retrying, replication and checkpoint as fault-tolerance techniques. These mechanisms can be applied in a flexible manner, and be combined in order to meet different scenarios of resource availability. In this paper we describe the MAG architecture and what it can do in a volunteer computing environment. We also present a description of these mechanisms and a performance evaluation in a real world environment.

[11] Marcos E. B. Broinizi, João Eduardo Ferreira, and Alfredo Goldman. Using annotations in the naked objects framework to explore data requirements. In SAC '08: Proceedings of the 2008 ACM symposium on Applied computing, pages 630-637, Fortaleza, Ceara, Brazil, 2008. ACM. [ bib | html ]
The creation of conceptual data design that appropriately represents specific application domain is one of the main challenges in requirements engineering. An initiative to help designers is the Naked Objects framework, where it is possible to interact with conceptual model in a limited way. The interactions are restricted to entity creations and single object-relations. We created an extension of the Naked Objects framework using annotations to allow manipulation of higher level abstractions as specialization and object-relationship. These abstractions allow better interactions between the domain specialist and designers. The use of our approach to explore and validate data requirements has several benefits: 1) It reduces conceptual specification problems (like poorly data requirements identification); 2) It narrows the distance among domain and design specialists; 3) It allows the simultaneous exploration of the conceptual data design and the system requirements.

Keywords: Agile methods of software development, conceptual data design, data abstractions, requirements engineering, requirements specification
[12] Márcio V. Santos, Alexandre Takinami, Thiago Thies, Alfredo Goldman, and Carlos Eduardo Manssur. Tail - A Java Technical Analysis Library. In Workshop de Software Livre, Porto Alegre, Brazil, 2008. [ bib | pdf ]
Technical Analysis studies forecasting future price trends with the objective to find out the best moment to buy and sell shares. The Tail's target is to develop a Java Open-Source library that abstracts the basic components of Technical Analysis, supplying tools for creation, manipulation and evaluation of strategies to buy and sell. The objective of this paper is to present the Tail library, its architecture and results obtained. The library is validaded with several post-mortem experiments.

[13] Alfredo Goldman and Yanik Ngoko. A MILP Approach to Schedule Parallel Independent Tasks. In ISPDC '08: International Symposium on Parallel and Distributed Computing, pages 115-122, Cracóvia, 2008. IEEE Computer Society. [ bib ]
We propose a new Mixed Integer Linear Programmingapproach to solve the classical problem of scheduling independent parallel tasks without preemption. We proposea formulation where the goal is to minimize the makespan. Then we show the flexibility of this approach by extendingthe result to the contiguous case. We validate this approachwith some experiments on the execution times and comparingthe optimal results with the solutions provided by list algorithms.

[14] Márcio V. Santos, Alexandre Takinami, Alfredo Goldman, and Cecilia Fernandes. Tail - A Java Technical Analysis Library. In CSE '08: Proceedings of the 2008 11th IEEE International Conference on Computational Science and Engineering, pages 463-470, Washington, DC, USA, 2008. IEEE Computer Society. [ bib | html ]
Technical Analysis explores forecasting of future price trends with the objective of identifying the best moment to buy and sell shares. Tail consists of a Java Open-Source library that abstracts the basic components of Technical Analysis, supplying tools for creation, manipulation and evaluation of techniques to buy and sell shares. We developed Tail's structure in a extensible and adaptable way, allowing its use as an environment for simulation and study of new techniques of chart analysis. This paper presents the Tail library, its architecture and results obtained with its use. We validate the library through an experimental section with several post-mortem experiments.

[15] Hugo Corbucci and Alfredo Goldman. Open Source and Agile: Two worlds that should have a closer interaction. In ESELAW - V Experimental Software Engineering Latin American Workshop, Salvador, Brazil, 2008. [ bib | html ]
Agile methods and open source software communities share similar cultures with different approaches to overcome problems. Although several professionals are involved in both worlds, neither agile methodologies are as strong as they could be in open source communities nor those communities provide strong contributions to agile methods. This work identifies and exposes the obstacles that separate those communities in order to extract the best of them and improve both sides with suggestions of tools and development processes.

[16] Mariana Kolberg, Daniel Cordeiro, Alfredo Goldman, Gerd Bohlender, and Luiz Fernandes. A Multithreaded Verified Method for Solving Linear Systems in Dual-Core Processors. In Workshop on State-of-the-Art in Scientific and Parallel Computing, Trondheim, 2008. Proceedings of the Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA 2008). [ bib ]
This paper presents a new multithreaded approach for the problem of solving dense linear systems with verified results. We propose a new method that allows our algorithm to run in a dual-core system without making any changes in the floating-point rounding mode used during the computations, i.e., each processor independently uses its own floating-point rounding strategy to do the computations. The algorithm distributes the computational tasks among the processors based on the floating-point rounding mode required by the task.

[17] Daniel Cordeiro, Alfredo Goldman, and Denis Trystram. Implicit Cooperation in Multi-Organization Clusters. In XXI European Chapter on Combinatorial Optimization, pages 24-25, Dubrovnik, 2008. Proceedings of the XXI European Chapter on Combinatorial Optimization. [ bib ]
Commodity hardware and the maturity of grid middleware systems available today allow the development of large distributed systems composed by many parallel jobs. In order to fully utilize the available hardware and get the best performance, we need a sophisticated scheduling model that can respect the cluster owner's best interest and, at the same time, achieve global performance goals.

Grid computing systems are composed by organizations that own clusters of computers. A grid user submit his/her jobs to a scheduler system that can choose any machine available in any of these clusters. However, each organization (a university lab, for instance) that shares its resources wants to take maximum advantage of its own hardware. In order to improve cooperation between organizations, local jobs must be prioritized.

The scheduling of the jobs in the available grid machines is a crucial problem. Although each user submits jobs locally in his/her own organization, it is necessary to optimize the allocation of the jobs for the whole platform in order to achieve good performance.

Pascual et al. proposed a preliminary analysis of the scheduling problem of rigid parallel tasks in multi-organization, homogeneous clusters. In their work, they proposed a new algorithm that, using an initial scheduling using Highest First order done locally by each organization, produces a global schedule that does not delay the local makespan of any organization. Their main contribution was an algorithm for this centralized global controller that can always be profitable. They showed that their algorithm is a 3-approximation which is asymptotically the best that can be obtained for this specific problem.

In this work, we extend the results obtained by Pascual et al. to organizations that run sequential jobs. Starting from the heuristic proposed by Pascual, we study the effects of allowing each organization to choose its own scheduling objective (such as total completion time and sum of completion times) in the global scheduling.

[18] Alex Camargo and A. Goldman. Análise e disposição de recursos de rede em grades computacionais. In VI Workshop on Grid Computing and Applications, pages 153-154, Rio de Janeiro, 2008. Proceedings of the VI Workshop on Grid Computing and Applications. [ bib ]
Arcabouços de grades computacionais têm se popularizado nos últimos anos, por serem uma proposta concreta para gerenciamento e uso de recursos distribuídos. Alguns destes arcabouços, como o Integrade, tem como característica permitir a execução de aplicações paralelas fortemente acopladas, onde a otimização de comunicação é fator crucial de desempenho das aplicações. Neste artigo apresentamos um estudo sobre inferência de topologia física das redes locais que formam o arcabouço de grade, de forma a prover dados para que o algoritmo de escalonamento aloque as tarefas da melhor forma possível.

[19] A. Goldman, Y. Ngoko, and D. Trystram. Combining numerical iterative solvers. In 5th International workshop on Parallel Matrix Algorithms and Applications (PMAA), pages 17-18, Neuchatel, Switzerland, 2008. Proceedings of the 5th International Workshop on Parallel Matrix Algorithms and Appications. [ bib | pdf ]
Given a linear system there are several solvers which can be used to solve it. However, according to the properties of the linear system different solvers may have different convergence speeds, or may even not converge at all. Nevertheless, it can be difficult to verify these properties in practice, mainly due to rounding errors, and there are also some cases where no direct property can be used. In this special situations there is no easy choice on the best solver, so instead of determining it, we are interest in finding good combinations of the solvers.

We are interested by the resolution of sparse systems with three solvers based on three different iterative methods. The numerical methods used are the Conjugate Gradient (CG) method, the BiConjugate Gradient Stabilized (BiCGSTAB) method and the Transpose Free Quasi Minimal Residual Method (TFQMR).

To combine numerical solvers, we use an approach based on algorithm portfolio. The basic idea is to interleave iterations of numerical solvers in cycles which are executed until one solver finds a solution. We first study the combination of numerical solvers in an offline setting. In this setting we suppose that a representative set of all linear systems is available. The goal is to combine the set of numerical solvers in order to minimize the average completion time.

Then, we study the combination in an on-line setting. In this setting, we do not suppose any previous knowledge. Some heuristics are presented. The first heuristic periodically executes a same cycle of iterations for each numerical solvers. The other heuristics adapts their cycles of iterations from convergence informations gathered from previous cycles. The main difficulty in these latter cases is to define metrics and rules that will be used to evaluate the convergence of previous cycles and to define next cycles.

We experiment our approaches using the SPARSKIT library. We present comparisons among heuristics and solvers, and we also study the impact of the cycle size on the execution times.

[20] Eduardo Guerra and Alfredo Goldman. Tool and Application Experiences with the Grid Application Toolkit (GAT). In CCGrid 2007 - Posters, 2007, Rio de Janeiro, 2008. Proceedings of the 5th International Workshop on Parallel Matrix Algorithms and Appications. [ bib ]
The establishment of Grid computing resulted in the deployment of several infrastructures and tools. However, this diversity is at the same time one of the major strengths and a big challenge of the grid. Although the Global Grid Forum (GGF) aims at a global standardization, these efforts will take time so users and developers will have to deal with such diversity for a while. In this paper, we report our experience with the Grid Application Tookit (GAT), a grid programming interface for tools and applications which abstract the grid technology diversity. We describe the development of an integrated and extensible development environment (IDE) for the Grid. We also present the deployment on the InteGrade middleware of a GAT application originally written for the Globus middleware.

[21] Daniel Cordeiro, Alfredo Goldman, and Dilma da Silva. Load Balancing on an Interactive Multiplayer Game Server. In Anne-Marie Kermarrec, Luc Bougé, and Thierry Priol, editors, Euro-Par 2007 Parallel Processing, volume 4641 of Lecture Notes in Computer Science, pages 184-194. Springer, 2007. [ bib | html ]
In this work, we investigate the impact of issues related to performance, parallelization, and scalability of interactive, multiplayer games. Particularly, we study and extend the game QuakeWorld, made publicly available by id Software under GPL license. We have created a new parallelization model for Quake's distributed simulation and implemented this model in QuakeWorld server. We implemented the model adapting the QuakeWorld server in order to allow a better management of the generated workload. We present in this paper our experimental results on SMP computers.

[22] Danilo Sato, Alfredo Goldman, and Fabio Kon. Tracking the Evolution of Object Oriented Quality Metrics. In 8th International Conference on Extreme Programming and Agile Processes in Sofware Engineering XP'2007, pages 84-92, Como, Italy, 2007. [ bib | pdf ]
The automated collection of source code metrics can help agile teams to understand the software they are producing, allowing them to adapt their daily practices towards an environment of continuous improvement. This paper describes the evolution of some object-oriented metrics in several agile projects we conducted recently in both academic and governmental environments. We analyze seven different projects, some where agile methods were used since the beginning and others where some agile practices were introduced later. We analyze and compare the evolution of such metrics in these projects and evaluate how the different project context factors have impacted the source code.

[23] Julian Monteiro, Alfredo Goldman, and Afonso Ferreira. Using Evolving Graphs Foremost Journeys to Evaluate Ad-Hoc Routing Protocols. In 25th Brazilian Symposium on Computer Networks (SBRC 07), pages 17-30, Belém, Brazil, 2007. [ bib ]
The performance evaluation of routing protocols for ad hoc networks is a difficult task. However, a graph theoretic model - the evolving graphs - was recently proposed to help capture the behavior of dynamic networks with fixed-schedule behavior. Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we design a new congestion avoidance mechanism and a modified end-to-end delay metric in order to improve the evolving graph based routing protocol proposed previously. We use the NS2 network simulator to compare this new version to the three protocols provided by NS2, namely AODV, DSR and DSDV, and to OLSR, which is included in the experiments for the first time.

[24] Afonso Ferreira, Alfredo Goldman, and Julian Monteiro. On the Evaluation of Shortest Journeys in Dynamic Networks. In Intl. Symposium on Networking Computing and Applications (NCA'07), Cambridge, 2007. [ bib ]
The assessment of routing protocols for wireless networks is a difficult task, because of the networks' highly dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low earth orbit (LEO) satellites systems, have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic, which may make them easier to study. The graph theoretic model - the evolving graphs - was proposed to help capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms.

Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we evaluated the shortest journey evolving graph algorithm when used in a routing protocol for MANETs. We use the NS2 network simulator to compare this first implementation to the four well known protocols, namely AODV, DSR, DSDV, and OLSR. In this paper we present simulation results on the energy consumption of the nodes. We also included other EG protocol, namely EGForemost , in the experiments.

[25] Danilo Sato, Dairton Bassi, and Alfredo Goldman. Extending Extreme Programming With Practices From Other Agile Methodologies. In 1st Workshop on Rapid Application Development (WDRA'2007) in the Brazilian Symposium on Software Quality, Porto de Galinhas, Brazil, 2007. [ bib | slides | pdf ]
In the second edition of Extreme Programming Explained, Kent Beck breaks the original twelve practices in thirteen primary practices and eleven corollary practices. He also clearly outlines the principles of the methodology that should serve as guidelines when translating values into practices. Based on these principles and on our experience, we present five practices that we created, adapted, or brought from different agile methodologies and that we have been using on several projects: Daily Stand-up Meetings, Retrospectives, Refactoring Threshold, Story/Task Board, and Personas. For each practice we explain its use and we present the associated principles and values.

[26] Alexandre Freire, Alfredo Goldman, and Fábio Kon. The “Bootstrap” and “Split Personality” Antipractices - eXPeriences Teaching eXtreme Programming. In 1st Workshop on Rapid Application Development (WDRA'2007) in the Brazilian Symposium on Software Quality, Porto de Galinhas, Brazil, 2007. [ bib | slides | pdf ]
This article provides insight into two simple and common problems when teaching XP: the “Bootstrap” and “Split Personality” antipractices. Bootstrap describes how teams have difficulties starting a project with little or no code base. Split Personality describes difficulties experienced when one assumes both the Coach and Customer roles. We present these organizational antipatterns as antipractices we have identified while teaching XP in different contexts. We discuss simple solutions to the antipatterns based on reflections from these experiences and describe concrete situations where they were effective.

[27] E. Guerra and Alfredo Goldman. InGriDE: um ambiente de desenvolvimento para computação em grade baseado no GAT (Grid Application Toolkit). In V Workshop de Computação em Grade e Aplicações em conjunto com o SBRC 2007, Belém, Brazil, 2007. [ bib | slides ]
The establishment of Grid Computing resulted in the deployment of several infrastructures which provide computational resources for solving complex problems. However, developing applications over this heterogeneous and distributed infrastructure is still a complex and error prone process. This paper introduces InGriDE, an integrated and extensible development environment for Grid Computing which aims to reduce this problem. InGriDE unifies tools and provide interaction with different middleware systems through the Grid Application Toolkit (GAT) programming interface. In this paper we present the main contributions of InGriDE for Grid Computing.

[28] P. Esmério, F. Raganhan, H. Posca, and A. Goldman. O uso de ferramentas colaborativas on-line no ensino de graduação. In II Simposio de iniciação científica e pós-graduação do IME-USP. Anais do II Simposio de iniciação científica e pós-graduação do IME-USP, 2007. [ bib ]
[29] J. Monteiro, A. Goldman, and A. Ferreira. Performance Evaluation of Dynamic Networks using an Evolving Graph Combinatorial Model. In 2nd IEEE International Conference on Wireless and Mobile Computing, Networking and Communications WiMob'06, pages 173-180, Montreal, 2006. IEEE Computer Society. [ bib | html ]
The highly dynamic behavior of wireless networks make them very difficult to evaluate, e.g. as far as the performance of routing algorithms is concerned. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low Earth orbit (LEO) satellites systems have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study on the uses of these theoretical results into practical situations. Therefore, the objective of this work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we used the NS2 network simulator to first implement an evolving graph based routing protocol, and then to evaluate such protocol compared to three major ad-hoc protocols (DSDV, DSR, AODV). Interestingly, our experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like stochastically predictable behavior. We also discuss such issues in this paper, as a result of our experience.

Keywords: NS2 network simulator, combinatorial model, dynamic behavior, evolving graph theory, graph theoretic model, performance evaluation, routing protocol, stochastic prediction, wireless network, graph theory, performance evaluation, prediction theory, radio networks, routing protocols, stochastic processes
[30] Marcelo Vinagreiro and Alfredo Goldman. Um sistema distribuído para busca de caminhos em grafos dinâmicos. In WSCAD VII Workshop em Sistemas Computacionais de Alto Desempenho, Ouro Preto, 2006. Anais do VII WSCAD. [ bib | pdf ]
Este trabalho descreve um novo modelo para cálculo concorrente de caminhos em grafos dinâmicos os quais podem estar particionados em um conjunto de servidores interconectados. Aspectos dinâmicos em cálculos de caminhos têm sido bem explorados em trabalhos anteriores, neste trabalho, consideramos também aspectos de distribuição. O arcabouco proposto pode ser usado com algoritmos de cálculo de caminhos dinâmicos ou estáticos. O modelo pode ser usado em sistemas simulando o estado de uma rede ou o monitormento das condicoes de trânsito de uma cidade. O artigo também apresenta alguns detalhes de implementação bem como resultados de testes.

[31] Pierre-François Dutot, Marco A. S. Netto, Alfredo Goldman, and Fabio Kon. Scheduling moldable BSP tasks. In Proceedings of the 11th Workshop on Job Scheduling Strategies for Parallel Processing, volume 3834, pages 157-172, Boston, 2005. Workshop on Job Scheduling Strategies for Parallel Processing - LNCS. [ bib ]
Our main goal in this paper is to study the scheduling of parallel BSP tasks on clusters of computers. We focus our attention on special characteristics of BSP tasks, which can use fewer processors than the original required, but with a particular cost model. We discuss the problem of scheduling a batch of BSP tasks on a fixed number of computers. The objective is to minimize the completion time of the last task (makespan). We show that the problem is difficult and present approximation algorithms and heuristics. We finish the paper presenting the results of extensive simulations under different workloads.

[32] Raphael Y. De Camargo, Fabio Kon, and Alfredo Goldman. Portable checkpointing and communication for BSP applications on dynamic heterogeneous Grid environments. In SBAC-PAD'05: The 17th International Symposium on Computer Architecture and High Performance Computing, volume 1, pages 226-233, Rio de Janeiro, 2005. Workshop on Job Scheduling Strategies for Parallel Processing - LNCS. [ bib | html ]
Executing long-running parallel applications in Opportunistic Grid environments composed of heterogeneous, shared user workstations, is a daunting task. Machines may fail, become unaccessible, or may switch from idle to busy unexpectedly, compromising the execution of applications. A mechanism for fault-tolerance that supports these heterogeneous architectures is an important requirement for such a system. In this paper, we describe the support for fault-tolerant execution of BSP parallel applications on heterogeneous, shared workstations. A precompiler instruments application source code to save state periodically into checkpoint files. In case of failure, it is possible to recover the stored state from these files. Generated checkpoints are portable and can be recovered in a machine of different architecture, with data representation conversions being performed at recovery time. The precompiler also modifies BSP parallel applications to allow execution on a Grid composed of machines with different architectures. We implemented a monitoring and recovering infrastructure in the InteGrade Grid middleware. Experimental results evaluate the overhead incurred and the viability of using this approach in a Grid environment.

[33] R.M. Barbosa, Alfredo Goldman, and Fábio Kon. A Study of Mobile Agents Liveness Properties on MobiGrid. In Mobility Aware Technlogies and Applications (MATA'2005), volume 1, pages 30-34, Montreal, 2005. Mobility Aware Technlogies and Applications Companion Proceedings to LNCS 3744. [ bib ]
MobiGrid is a framework for mobile agents support within a grid computing environment. The mobile agents may be used to encapsulate long-processing applications (tasks). In MobiGrid, to provide a fast method of releasing the local machine and to prevent the tasks from dying suddenly, it is possible to have two or more copies of these tasks running independently; this concept is defined as liveness. In this paper, our goal is to simulate a network of personal workstations and the tasks that will be executed on them. In this way, we can study the effects of different liveness degrees on the completion time of the tasks.

[34] Andrei Goldchleger, Alfredo Goldman, Ulisses Hayashida, and Fabio Kon. The implementation of the BSP parallel computing model on the InteGrade Grid middleware. In MGC '05: Proceedings of the 3rd international workshop on Middleware for grid computing, volume 117, pages 1-6, Grenoble, France, 2005. ACM. [ bib | html ]
InteGrade is an object-oriented grid middleware infrastructure whose goal is to leverage existing computational resources in organizations. Rather than relying on dedicated hardware such as reserved clusters, InteGrade focuses on using desktops in users' offices, machines in computer laboratories, shared workstations, as well as dedicated clusters. In this paper, we describe the support for the execution of highly coupled parallel applications on top of InteGrade. The paper describes the implementation of the middleware to support BSP parallel applications (with global synchronization points), and presents experimental results.

Keywords: BSP, Parallel Computing, Grid Computing
[35] R.M. Barbosa and A. Goldman. MobiGrid: framework for mobile agents on computational grid environments. In III Workshop on Grid Computing and Applications, Petrópolis, 2005. Anais do III Workshop on Grid Computing and Applications. [ bib ]
This project focuses on the implementation of a framework for mobile agents support within a grid environment project, namely InteGrade. Our goal is to present a framework where time consuming sequential tasks can be executed using mainly the idle cycles of a network of personal workstations. The mobile agents may be used to encapsulate long processing applications (tasks). These agents can migrate whenever the local machine is requested by its user, since they are provided with automatic migration capabilities. Our framework also provides to the user a manager that keeps track of the agents submitted by him.

[36] Alfredo Goldman and Rodrigo M. Barbosa. MobiGrid: Framework for Mobile Agents on Computer Grid Environments. In MATA 2004, First International Workshop on Mobility Aware Technologies and Applications, pages 147-157, Florianópolis, 2004. Springer-Verlag. [ bib | pdf ]
This project focuses on the implementation of a framework for mobile agents support within a grid environment project, namely InteGrade. Our goal is to present a framework where time consuming sequential tasks can be executed using mainly the idle cycles of a network of personal workstations. The mobile agents may be used to encapsulate long processing applications (tasks). These agents can migrate whenever the local machine is requested by its user, since they are provided with automatic migration capabilities. Our framework also provides to the user a manager that keeps track of the agents submitted by him.

[37] Alexandre Freire, Alfredo Goldman, Carlos Eduardo Ferreira, Christian Asmussen, and Fábio Kon. Mico - university schedule planner. In Anais do 5o Workshop sobre Software Livre, pages 147-150, Porto Alegre, Brazil, 2004. Anais do WSL'2004. [ bib | pdf ]
This paper describes the development of Mico, the XPUSP University Schedule Planner. It is a system that manages the creation of a schedule for the courses of the Computer Science department and the allocation of professors to teach these courses based on preferences gathered from professors and students. It has been developed using free software and it is itself free software, available under the GNU GPL. We will give a short description of the problem we want to solve and how the system works, then we will discuss the free software frameworks and tools used in the development and our interaction with the free software development community.

[38] Raphael Y. de Camargo, Andrei Goldchleger, Fabio Kon, and Alfredo Goldman. Checkpointing-based rollback recovery for parallel applications on the InteGrade grid middleware. In MGC '04: Proceedings of the 2nd workshop on Middleware for grid computing, pages 35-40, Vancouver, Canada, 2004. ACM. [ bib | html ]
InteGrade is a grid middleware infrastructure that enables the use of idle computing power from user workstations. One of its goals is to support the execution of long-running parallel applications that present a considerable amount of communication among application nodes. However, in an environment composed of shared user workstations spread across many different LANs, machines may fail, become unaccessible, or may switch from idle to busy very rapidly, compromising the execution of the parallel application in some of its nodes. Thus, to provide some mechanism for fault-tolerance becomes a major requirement for such a system. In this paper, we describe the support for checkpoint-based rollback recovery of parallel BSP applications running over the InteGrade middleware. This mechanism consists of periodically saving application state to permit to restart its execution from an intermediate execution point in case of failure. A precompiler automatically instruments the source-code of a C/C++ application, adding code for saving and recovering application state. A failure detector monitors the application execution. In case of failure, the application is restarted from the last saved global checkpoint.

Keywords: Fault-tolerance, Checkpointing, BSP, Grid Computing
[39] Alfredo Goldman and Leonardo Pinho. Sistemas de localização dinâmica de serviços em ambientes de computação móvel. In WCSF2003 - Workshop de Computação Móvel e Sem Fio, São Lourenço, MG, Brazil, 2003. Workshop de Computação Móvel e Sem Fio, 2003. [ bib ]
Um dos desafios atuais, com o aumento do número de serviços em uma rede, é a localização dinâmica dos mesmos. Várias tecnologias de localização de serviços foram desenvolvidas para simplificar o uso dos mesmos, permitindo que eles sejam encontrados, configurados e usados com um mínimo de esforço. Entretanto, não existe nenhum sistema que selecione o servidor mais conveniente ao cliente, como o mais próximo a este. Apresentamos uma solução para estender os sistemas existentes, integrando-os com sistemas de localização física de unidades móveis, a fim de localizar o serviço mais próximo ao cliente.

[40] Martha Torres, Alfredo Goldman, and Junior Barrera. A Parallel Algorithm for Enumerating Combinations. In International Conference on Parallel Processing, volume 1, pages 518-526, Taiwan, 2003. IEEE Computer Society. [ bib | html ]
In this paper we propose an efficient parallel algorithm with simple static and dynamic scheduling for generating combinations. It can use any number of processors (NP <=n - m + 1) in order to generate the set of all combinations of C(n, m). The main characteristic of this algorithm is to require no integer larger than n during the whole computation. The performance results show that even without a perfect load balance, this algorithm has very good performance, mainly when n is large. Besides, the dynamic algorithm presents a good performance on heterogeneous parallel platforms.

Keywords: combinations enumeration, dynamic algorithm, dynamic scheduling, heterogeneous parallel platforms, load balance, parallel algorithm, static scheduling, computational complexity, dynamic scheduling, parallel algorithms, processor scheduling, resource allocation
[41] Andrei Goldchleger, Fabio Kon, Alfredo Goldman, and Marcelo Finger. Integrade: Object-Oriented Grid Middleware Leveraging Idle Computing Power of Desktop Machines. In Third IFIP Conference on E-Commerce, E-Business and E-Goverment, pages 610-616, Guarujá, Brazil, 2003. Proceedings of the Third IFIP Conference on E-Commerce, E-Business and E-Goverment. [ bib | html ]

Keywords:
[42] Alfredo Goldman and Carlos Queiroz. A model for parallel job scheduling on dynamical computer grids. In ACM/IFIP/USENIX Middleware'2003 Workshop on Middleware for the Grid, pages 264-266, Rio de Janeiro, Brazil, 2003. Rio de Janeiro : PUC-Rio. [ bib ]
This work presents a model that allows the execution of parallel applications in a grid environment. Our main focus is on how to share the idle cycles of clusters and computers to execute parallel applications. We introduce a new model with the notions of locality and adaptability. The locality is used for job allocation, and for job migration. The adaptability provides a simple mechanisn to allow clusters to join or leave a grid. We also propose a middleware architecture to implement the model.

[43] A. Goldman, F. Kon, M. Finger, and A. Goldchleger. InteGrade: Object-Oriented Grid Middleware Leveraging Idle Computing Power of Desktop Machines. In ACM/IFIP/USENIX Middleware'2003 Workshop on Middleware for the Grid, pages 232-234, Rio de Janeiro, Brazil, 2003. Rio de Janeiro : PUC-Rio. [ bib ]
Grid computing technology improves the computing experiences at organizations by effectively integrating distributed computing resources. However, just a small fraction of currently available Grid infrastructures focuses on reutilization of existing commodity computers. This paper introduces InteGrade, a novel object-oriented middleware Grid infrastructure that focuses on leveraging the idle computing power of shared desktop machines. Its features include support for a wide range of parallel applications and mechanisms to assure that owners of shared resources do not perceive any loss in the quality of service. A prototype implementation is under construction and the current version is available for download.

[44] Alfredo Goldman, Fabio Kon, and Carlos Ferreira. Programação eXtrema: uma experiência didática. In Curso de Qualidade 2002, volume 1, pages 63-72, Florianópolis, 2002. Anais do VI Curso de Qualidade SBC 2002. [ bib ]

Keywords:
[45] Flávio Arruda and Alfredo Goldman. Eliminação Paralela de Termos Dominantes no Problema da Mochila. In Workshop de Sistemas Computacionais de Alto Desempenho, pages 89-94, Vitória, ES, Brazil, 2002. Sociedade Brasileira da Computação. [ bib ]
Um dos problemas mais conhecidos em otimização combinatória é o problema da mochila ilimitado. Devido a sua importância diversos autores buscaram formas eficientes de resolvê-lo. Por um lado, diversos estudos da paralelização deste problema foram feitos. Por outro lado, várias técnicas de eliminação de objetos também foram encontradas. Neste trabalho nós unimos as duas possibilidades apresentando algoritmos paralelos para a eliminação de objetos. Para validação dos algoritmos, os mesmos foram implementados em Java e executados em um cluster de computadores.

[46] Alfredo Goldman. Scalable Algorithms for Complete Exchange on Multi-Cluster Networks. In 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, pages 286-287, Berlin, Germany, 2002. IEE/ACM CCGrid 2002. [ bib ]
Inside a dedicated parallel computer the communication times were generally modeled in the same way, independently of which processors communicate. In a network where the links among the computers are heterogeneous, or in hierarchical clusters, this might not be true anymore. Computers that have faster links, or are closer to each other should be able to exchange messages faster. These differences on communication times should be considered, not only for attributing tasks to the processors but also in global synchronization/communication. The goal of this paper is to study irregular all-to-all communications in a network of dedicated clusters.

[47] Alfredo Goldman and C. Rapine. Scheduling with Duplication on m Processors with Small Communication Delays. In Brazilian Symposium on Graphs Algorithms and Combinatorics, volume 7, pages 1-4, Fortaleza, Brazil, 2001. Electronic Notes in Discrete Mathematics. [ bib ]
We consider the problem of scheduling a directed acyclic graph on a limited number of processors in presence of communication delays (P | prec, ci,j | Cmax). Under the small communication time assumption, meaning that the communication delays are smaller than the computation times of the tasks, we propose a new list scheduling algorithm. This algorithm takes advantage of the duplication to reduce the impact of the communication on the schedule makespan. We establish for this algorithm a worst case performance guarantee of 2 compared to an optimal solution.

Keywords: Scheduling, communication delays, performance guarantee
[48] A. Goldman and A. Santiago. Políticas de hand-off com balanceamento de carga para computação móvel. In Workshop de Comunicação sem Fio e Computação Móvel, Recife, Brazil, 2001. Anais do 3o. Workshop de Comunicação sem Fio e Computação Móvel. [ bib ]
Usually the hand-off is done when the mobile units move from one base station to other. As there exist regions where more than one base station is available. We propose a new scheme where the hand-off can be initiated by the base stations. The goal of this scheme is to balance the load among the base stations.

[49] Alfredo Goldman. Scheduling communications on a multi-cluster networks. In New trends in scheduling for parallel and distributed systems, Marseille, 2001. Book of Abstracts - New trends in scheduling for parallel and distributed systems. [ bib | pdf ]
Nowadays, with the introduction of clusters of computers the notion of interprocessor communication is of growing interest. Inside a dedicated cluster the communication times were generally modeled in the same way, independently of which processors communicate. In a network where the links among the computers are heterogeneous this might not be true anymore. Computers that have faster links, or are closer with each other should be able to exchange messages faster. These differences on communication times should be considered, not only for attributing tasks to the processors but also in global synchronization/communication. The goal of this paper is to study the global communication in a network of dedicated clusters. We propose new communication algorithms based on known algorithms and we present simulations on their expected performances.

Keywords: Scheduling of communication, BSP-like synchronization, global communication
[50] A. Goldman and G. Mounie. Near optimal scheduling of UET-task chains on m BSP processors. In Rencontres Francophones du Paralelisme, pages 239-242 (in French), Bordeaux, 1998. REMPAR'98, 1998. [ bib | .ps ]
Nous présentons tout d'abord le modèle BSP et le problème de l'ordonnancement de chaînes indépendantes. Puis nous nous attacherons à l'étude de la complexité do problème et à la présentation d'un algorithme approché.

Keywords: Ordonnancement, chaînes, BSP
[51] Alfredo Goldman, Joseph G. Peters, and Denis Trystram. Exchange of messages of different sizes. In Irregular, 1998, volume 1457, pages 194-205, Berkeley, 1998. Springer Verlag. [ bib | .ps ]
In this paper, we study the exchange of messages among a set of processors linked through an interconnection network. We focus on general, non-uniform versions of all-to-all (or complete) exchange, problems in asynchronous systems with a linear cost model and messages of arbitrary sizes. We extend previous complexity results to show that the general asynchronous problems are em NP-complete. We present several approximation algorithms and determine which heuristics are best suited to several parallel system. We conclude with experimental results that show that our algorithms outperform the native all-to-all exchange algorithm on an IBM SP2 when the number of processors is odd.

[52] Alfredo Goldman and Denis Trystram. Algorithms for the message exchange problem. In Parelec, 1998, pages 153-161, Byalistok, 1998. [ bib | .ps ]
In a distributed memory computer system, the tasks of a parallel program spread among the processors have to communicate in order to exchange data. The communication phase can be seen as a h-relation whose efficient implementation allow a high performance execution of a large class of algorithms. We apply some well known linear algebra algorithms to find communication patterns, that have a very good performance in practice.

Keywords: Personalized communication, routing h-relations, BSP model
[53] Alfredo Goldman, Greégory Mounié, and Denis Trystram. Near Optimal Scheduling of UET-task chains on m BSP processors. In High Performance Computing, Madras, 1998. HiPC'98. [ bib | .ps ]
The aim of this work is to show that scheduling a set of independent chains on a parallel machine under the BSP model is a difficult optimization problem which can be easily approximated in practice. BSP is a machine independent computational model which is becoming more and more popular. Finding the optimal solution when the number of processors is fixed is shown to be hard. Efficient heuristics including communications are proposed and analyzed. We particularly focus on the influence of synchronization between consecutive supersteps. Simulations of a large number of instances have been carried out to complement the theoretical worst case analysis. They confirm the very good behavior of the algorithm on average.

[54] A. Goldman and D. Trystram. An efficient parallel algorithm for solving the knapsack problem on the hypercube. In Parallel Processing Symposium, 1997. Proceedings., 11th International, pages 608-615, Genebra, 1997. [ bib | html ]
The authors present a new algorithm to solve the integral knapsack problem on the hypercube. The main idea is to use the fact that the precedence graph of the dynamic programming function of the knapsack problem is an irregular mesh. They propose a scheduling algorithm for irregular meshes on the hypercube. The efficiency of the algorithm is independent on the number of processors. They also present some improvements for the solution of the 0/1 knapsack problem on the hypercube

Keywords: 0/1 knapsack problem solving, dynamic programming function, efficient parallel algorithm, hypercube, integral knapsack problem solving, irregular mesh, irregular meshes, precedence graph, scheduling algorithm, dynamic programming, graph theory, hypercube networks, parallel algorithms, processor scheduling
[55] A. Goldman and S. Fidanova. Parallel execution of irregular meshes into a linear systolic array. In 2nd International Conference on Parallel Procesing, pages 267-274, Zakopane, 1997. PPAM'97. [ bib | pdf ]
We present in this paper a scheduling algorithm for the execution of irregular meshes into a systolic linear array. The data dependence graphs of many problems in computer science are irregular meshes. These include the unbounded knapsack problem, the subset sum problem, the change making problem and the longest common subsequence problem. In this paper a scheduling algorithm for a dependence graph is represented by an allocation function and an initial time for each vertex. The allocation and timing function in this paper are improvements of the previous methods. Our method reaches two lower bounds, the lower bound on the number of processors and the lower bound on time.

Keywords: Irregular mesh, scheduling, systolic algorithm, regular interconnection networks.
[56] A. Goldman, J. Peters, and D. Trystram. Total Exchange with Messages of Different Sizes. In International Workshop on Interconnection Networks, Praga, 1997. IWIN'97. [ bib | html ]

[57] A. Ferreira, A. Goldman vel Lejbman, and S. Song. Bus based parallel computers: A viable way for massive parallelism. In Costas Halatsis, Dimitrios Maritsas, George Philokyprou, and Sergios Theodoridis, editors, PARLE'94 Parallel Architectures and Languages Europe, volume 817 of Lecture Notes in Computer Science, pages 553-564. Springer Berlin/Heidelberg, 1994. [ bib | html | .ps ]
In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point interconnection network. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems so as to improve the communication efficiency. In this paper we study global communication on parallel architectures where the communication means are constituted solely by busses. We focus on the hyperpath and the hypergrid architectures, which are the bus-based versions of the well used point-to-point linear and grid interconnection networks. Using (hyper) graph theoretic concepts in order to model inter-processor communication in such networks, we developed a new tool called simplification in order to give extremely efficient algorithms for gossiping (all-to-all or total exchange communications).

[58] A. Goldman, A. Ferreira, and S.W. Song. Comunicação em hipergrades e hipertoros usando barramentos. In V Simpósio Brasileiro de Arquitetura de Computadores, Florianópolis, 1993. SBAC PAD 93. [ bib | pdf ]

Technical works

[1] Alfredo Goldman, Joseph G. Peters, and Denis Trystam. Exchanging Messages of Different Sizes. Technical report, School of Computer Science, Simon Fraser University, September 2002. [ bib | pdf ]
This paper deals with the study of the exchange of messages among a set of processors linked through an interconnection network. We focus on general, non-uniform versions of message exchange problems in asynchronous systems with a linear cost model and messages of arbitrary sizes. We extend previous complexity results to show that the general asynchronous problems are NP-complete. We present several heuristics and determine which algorithms are best suited to several parallel systems. We propose new algorithms that combine the advantages of some of the heuristics. We conclude with experiments and simulations of the algorithms and analyses of their performances.

Keywords: Personalized communications, BSP model, communication primitives
[2] Andrei Goldchleger, Fabio Kon, Alfredo Goldman, Marcelo Finger, and Siang Wun Song. InteGrade: Rumo a um Sistema de Computação em Grade para Aproveitamento de Recursos Ociosos em Máquinas Compartilhadas. Technical report, Instituto de Matemática e Estatística, Universidade de São Paulo, September 2002. [ bib | pdf ]
Computational Grids are a new trend in distributed computing systems. They allow the sharing of geographically disributed resources in an efficient way, extending the boundaries of what we perceive as distributed computing. Various sciences can benefit from the use of Grids to solve CPU-intensive problems, creating potencial benefits to the entire society. With further developement of Grid technology, it is very likely that corporations, universities, and public institutions will exploit Grids to enhance their computing infrastructure. In recent years, there has been a large increase in Grid technology research, which has produced some reference Grid implementations. This technical report presents the main features of four major Grid projects: Globus, Legion, Condor, and BOINC. We describe the design principles and the most important aspects of each system from our point of view. Finally, we introduce a new research project started recently at the University of São Paulo: InteGrade. In this new research effort, we aim at extending previous Grid research by using advanced distributed object technologies to build a novel Grid infrastructure to enable the use of idle processing time in commodity workstations without loss of Quality of Service for workstation users.

Thesis

[1] Alfredo Goldman. Impact des modèles d'exécution pour l'ordonnancement en calcul parallèle. PhD thesis, Institut National Polythecnique de Grenoble, INPG, Grenoble, France, 1999. [ bib ]

[2] Alfredo Goldman. Novas Estruturas de Interconexão a base de Barramentos: Uma contribuíção a computação maciçamente paralela. Master's thesis, Universidade de São Paulo, USP, São Paulo, Brazil, 1994. My master thesis was awarded with the third place on the I Thesis Contest of the Latin American Congress of CLEI (Centro de Estudios Latinoamericanos en Informática), Mexico City, Mexico, September 1994, and with the first place on the VII Thesis Contest of the XIV Congress of The Brazilian Computer Society, Caxambu, August 1994. [ bib | pdf ]
In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point inter-connection network, usually modeled by a graph where processors are nodes and communications links are edges. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems. In this work we demonstrate the interest of parallel architectures where the communication means are constitured solely by busses. We study some point-to-point topologies, and their modeling by graphs. We also study algorithms for global communication and some previous works that use busses. We propose generalizations of the ring, grid, etc, which are the bus-based versions of the well used point-to-point linear and grid interconnection networks. We show how to use hypergraph concepts in order to model inter-processor communication in such networks and we give efficient algorithms for broadcast and gossiping. We developed a new tool called simplification. The ideia is to construct a graph, to be called simplified graph, from the original topology, so that it will become easy to describe and perform communication schemes. The simplification concept also allows us to use some already known communication algorithms for usual networks.

Other

[1] Hugo Corbucci and Alfredo Goldman. Open Source and Agile Methods: Two worlds closer than it seems. In Will Aalst, John Mylopoulos, Norman M. Sadeh, Michael J. Shaw, Clemens Szyperski, Alberto Sillitti, Angela Martin, Xiaofeng Wang, and Elizabeth Whitworth, editors, Agile Processes in Software Engineering and Extreme Programming, volume 48 of Lecture Notes in Business Information Processing, pages 383-384. Springer Berlin Heidelberg, 2010. [ bib | html ]
Agile methods and Free, Libre and Open Source Software communities have different approaches to produce high quality and successful software in different scenarios. This work presents two surveys, each one directed to one of the communities, aimed to identify communication issues encountered in each environment. The results provided point out to very different communities with common practices and behaviors but with very similar problems and view points to solve the issues encountered.

Keywords: agile methods, open source, distributed agile
[2] Mariana Bravo and Alfredo Goldman. Reinforcing the Learning of Agile Practices Using Coding Dojos. In Will Aalst, John Mylopoulos, Norman M. Sadeh, Michael J. Shaw, Clemens Szyperski, Alberto Sillitti, Angela Martin, Xiaofeng Wang, and Elizabeth Whitworth, editors, Agile Processes in Software Engineering and Extreme Programming, volume 48 of Lecture Notes in Business Information Processing, pages 379-380. Springer Berlin Heidelberg, 2010. [ bib | html ]
Agile practices such as pair programming or test driven development are best learned when they are actually performed rather than read about. However, an unexperienced learner on his own might take a long time and might make mistakes that could be avoided if he had some help. In this work, we present an activity known as Coding Dojo as a technique to reinforce the learning of some Agile practices. We describe this method and present a study that evaluates its effect on learning.

[3] A. Kraemer, K. Vilar, and Alfredo Goldman. Fault Tolerance using Redundant Gateway Protocols. In Escola Regional de Alto Desempenho de SP. ERAD-SP 2010, São Paulo, 2010. [ bib | pdf ]
The goal of this paper is to compare fault-tolerant protocols inside of redundancy gateway context. For this purpose, performance tests were conducted with specific protocols, like HSRP, VRRP and GLBP. The results indicate which protocol will recover more quickly from the interruption of the default gateway.

This file was generated by bibtex2html 1.95