Heterogeneous computing with an algorithmic skeleton framework

The Graphics Processing Unit (GPU) is present in almost every modern day personal computer. Despite its specific purpose design, they have been increasingly used for general computations with very good results. Hence, there is a growing effort from the community to seamlessly integrate this kind of devices in everyday computing. However, to fully exploit the potential of a system comprising GPUs and CPUs, these devices should be presented to the programmer as a single platform. The efficient combination of the power of CPU and GPU devices is highly dependent on each device’s characteristics, resulting in platform specific applications that cannot be ported to different systems. Also, the most efficient work balance among devices is highly dependable on the computations to be performed and respective data sizes. In this work, we propose a solution for heterogeneous environments based on the abstraction level provided by algorithmic skeletons. Our goal is to take full advantage of the power of all CPU and GPU devices present in a system, without the need for different kernel implementations nor explicit work-distribution.To that end, we extended Marrow, an algorithmic skeleton framework for multi-GPUs, to support CPU computations and efficiently balance the work-load between devices. Our approach is based on an offline training execution that identifies the ideal work balance and platform configurations for a given application and input data size. The evaluation of this work shows that the combination of CPU and GPU devices can significantly boost the performance of our benchmarks in the tested environments, when compared to GPU-only executions.

Managing innovation complexity: About the co-existence of innovation types

The purpose of this study is to contribute to the changing innovation management literature by providing an overview of different innovation types and organizational complexity factors. Aiming at a better understanding of effective innovation management, innovation and complexity are related to the formulation of an innovation strategy and interaction between different innovation types is further explored. The chosen approach in this study is to review the existing literature on different innovation types and organizational complexity factors in order to design a survey which allows for statistical measurement of their interactions and relationships to innovation strategy formulation. The findings demonstrate interaction between individual innovation types. Additionally, organizational complexity factors and different innovation types are significantly related to innovation strategy formulation. In particular, more closed innovation and incremental innovation positively influence the likelihood of innovation strategy formulation. Organizational complexity factors have an overall negative influence on innovation strategy formulation. In order to define best practices for innovation management and to guide managerial decision making, organizations need to be aware of the co-existence of different innovation types and formulate an innovation strategy to more closely align their innovation objectives.

Tax compliance and tax complexity in Portugal: essays on the perception of tax professionals

Tese de Doutoramento em Contabilidade.

An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds

For a given self-map f of M, a closed smooth connected and simply-connected manifold of dimension m ≥ 4, we provide an algorithm for estimating the values of the topological invariant Dm r [f], which equals the minimal number of r-periodic points in the smooth homotopy class of f. Our results are based on the combinatorial scheme for computing Dm r [f] introduced by G. Graff and J. Jezierski [J. Fixed Point Theory Appl. 13 (2013), 63–84]. An open-source implementation of the algorithm programmed in C++ is publicly available at http://www.pawelpilarczyk.com/combtop/.

Tradução e validação para o português do Medication Regimen Complexity Index

FUNDAMENTO: A complexidade da farmacoterapia consiste de múltiplas características do regime prescrito, incluindo o número de diferentes medicações no esquema, o número de unidades de dosagem por dose, o número total de doses por dia e os cuidados na administração dos medicamentos. O Medication Regimen Complexity Index (MRCI) é um instrumento específico, validado e utilizado para medir a complexidade da farmacoterapia, desenvolvido originalmente em língua inglesa. OBJETIVO: Tradução transcultural e validação desse instrumento para o português do Brasil. MÉTODOS: Foi desenvolvido um estudo transversal envolvendo 95 pacientes com diabete do tipo 2 utilizando múltiplas medicações. O processo de validação teve início pela tradução, retrotradução e pré-teste do instrumento, gerando uma versão adaptada chamada Índice de Complexidade da Farmacoterapia (ICFT). Em seguida foram analisados parâmetros psicométricos, incluindo validade convergente, validade divergente, confiabilidade entre avaliadores e teste-reteste. RESULTADOS: A complexidade da farmacoterapia medida pelo ICFT obteve média de 15,7 pontos (desvio padrão = 8,36). O ICFT mostrou correlação significativa com o número de medicamentos em uso (r = 0,86; p < 0,001) e a idade dos pacientes (r = 0,28; p = 0,005). A confiabilidade entre avaliadores obteve correlação intraclasse igual a 0,99 (p < 0,001) e a confiabilidade teste-reteste obteve correlação de 0,997 (p < 0,001). CONCLUSÃO: Os resultados demonstraram que o ICFT apresenta bom desempenho de validade e confiabilidade, podendo ser utilizado como ferramenta útil na prática clínica e em pesquisas envolvendo análise da complexidade da terapia.

Algorithmic assistance to the optimization process in vehicle routing problems

Magdeburg, Univ., Fak. für Maschinenbau, Diss., 2013

Polynomial-time complexity for instances of the endomorphism problem in free groups

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism Φ of F sending W to U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two- generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

The complexity of random ordered structures

"Vegeu el resum a l'inici del document del fitxer adjunt."

On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

Functional sphere profiling reveals the complexity of neuroblastoma tumor-initiating cell model.

Neuroblastoma (NB) is a neural crest-derived childhood tumor characterized by a remarkable phenotypic diversity, ranging from spontaneous regression to fatal metastatic disease. Although the cancer stem cell (CSC) model provides a trail to characterize the cells responsible for tumor onset, the NB tumor-initiating cell (TIC) has not been identified. In this study, the relevance of the CSC model in NB was investigated by taking advantage of typical functional stem cell characteristics. A predictive association was established between self-renewal, as assessed by serial sphere formation, and clinical aggressiveness in primary tumors. Moreover, cell subsets gradually selected during serial sphere culture harbored increased in vivo tumorigenicity, only highlighted in an orthotopic microenvironment. A microarray time course analysis of serial spheres passages from metastatic cells allowed us to specifically "profile" the NB stem cell-like phenotype and to identify CD133, ABC transporter, and WNT and NOTCH genes as spheres markers. On the basis of combined sphere markers expression, at least two distinct tumorigenic cell subpopulations were identified, also shown to preexist in primary NB. However, sphere markers-mediated cell sorting of parental tumor failed to recapitulate the TIC phenotype in the orthotopic model, highlighting the complexity of the CSC model. Our data support the NB stem-like cells as a dynamic and heterogeneous cell population strongly dependent on microenvironmental signals and add novel candidate genes as potential therapeutic targets in the control of high-risk NB.

Complexity and Bounded Rationality in Individual Decision Problemsing.

I develop a model of endogenous bounded rationality due to search costs, arising implicitly from the problems complexity. The decision maker is not required to know the entire structure of the problem when making choices but can think ahead, through costly search, to reveal more of it. However, the costs of search are not assumed exogenously; they are inferred from revealed preferences through her choices. Thus, bounded rationality and its extent emerge endogenously: as problems become simpler or as the benefits of deeper search become larger relative to its costs, the choices more closely resemble those of a rational agent. For a fixed decision problem, the costs of search will vary across agents. For a given decision maker, they will vary across problems. The model explains, therefore, why the disparity, between observed choices and those prescribed under rationality, varies across agents and problems. It also suggests, under reasonable assumptions, an identifying prediction: a relation between the benefits of deeper search and the depth of the search. As long as calibration of the search costs is possible, this can be tested on any agent-problem pair. My approach provides a common framework for depicting the underlying limitations that force departures from rationality in different and unrelated decision-making situations. Specifically, I show that it is consistent with violations of timing independence in temporal framing problems, dynamic inconsistency and diversification bias in sequential versus simultaneous choice problems, and with plausible but contrasting risk attitudes across small- and large-stakes gambles.

Measuring Tax Complexity

This paper critically examines a number of issues relating to the measurement of tax complexity. It starts with an analysis of the concept of tax complexity, distinguishing tax design complexity and operational complexity. It considers the consequences/costs of complexity, and then examines the rationale for measuring complexity. Finally it applies the analysis to an examination of an index of complexity developed by the UK Office of Tax Simplification (OTS).

Identification of case complexity and increased health care utilization in patients with rheumatoid arthritis.

OBJECTIVES: To document biopsychosocial profiles of patients with rheumatoid arthritis (RA) by means of the INTERMED and to correlate the results with conventional methods of disease assessment and health care utilization. METHODS: Patients with RA (n = 75) were evaluated with the INTERMED, an instrument for assessing case complexity and care needs. Based on their INTERMED scores, patients were compared with regard to severity of illness, functional status, and health care utilization. RESULTS: In cluster analysis, a 2-cluster solution emerged, with about half of the patients characterized as complex. Complex patients scoring especially high in the psychosocial domain of the INTERMED were disabled significantly more often and took more psychotropic drugs. Although the 2 patient groups did not differ in severity of illness and functional status, complex patients rated their illness as more severe on subjective measures and on most items of the Medical Outcomes Study Short Form 36. Complex patients showed increased health care utilization despite a similar biologic profile. CONCLUSIONS: The INTERMED identified complex patients with increased health care utilization, provided meaningful and comprehensive patient information, and proved to be easy to implement and advantageous compared with conventional methods of disease assessment. Intervention studies will have to demonstrate whether management strategies based on INTERMED profiles can improve treatment response and outcome of complex patients.