Data Structures and Algorithms

1603 Submissions

[7] viXra:1603.0386 [pdf] submitted on 2016-03-28 13:36:36

Communication Optimization of Parallel Applications in the Cloud

Authors: Carreño ED, Diener M, Cruz EHM, Navaux POA
Comments: 24 Pages.

One of the most important aspects that influences the performance of parallel applications is the speed of communication between their tasks. To optimize communication, tasks that exchange lots of data should be mapped to processing units that have a high network performance. This technique is called communication-aware task mapping and requires detailed information about the underlying network topology for an accurate mapping. Previous work on task mapping focuses on network clusters or shared memory architectures, in which the topology can be determined directly from the hardware environment. Cloud computing adds significant challenges to task mapping, since information about network topologies is not available to end users. Furthermore, the communication performance might change due to external factors, such as different usage patterns of other users. In this paper, we present a novel solution to perform communication- aware task mapping in the context of commercial cloud environments with multiple instances. Our proposal consists of a short profiling phase to discover the network topology and speed between cloud instances. The profiling can be executed before each application start as it causes only a negligible overhead. This information is then used together with the communication pattern of the parallel application to group tasks based on the amount of communication and to map groups with a lot of communication between them to cloud instances with a high network performance. In this way, application performance is increased, and data traffic between instances is reduced. We evaluated our proposal in a public cloud with a variety of MPI-based parallel benchmarks from the HPC domain, as well as a large scientific application. In the experiments, we observed substantial performance improvements (up to 11 times faster) compared to the default scheduling policies.
Category: Data Structures and Algorithms

[6] viXra:1603.0107 [pdf] replaced on 2016-03-15 08:00:02

Languages Varying in Time and the P x NP Problem

Authors: Valdir Monteiro dos Santos Godoi
Comments: 8 Pages. In english and portuguese. Published in Transactions on Mathematics (TM) Vol. 3, No. 1, January 2017, pp. 34-37

An original proof of P is not equal to NP.
Category: Data Structures and Algorithms

[5] viXra:1603.0074 [pdf] submitted on 2016-03-04 18:18:57

Dois Problemas Provando P <> NP - v1

Authors: Valdir Monteiro dos Santos Godoi
Comments: 7 Pages. Article written around 5 years ago. See also viXra 1603.0107: "Languages Varying in Time and the Problem P x NP".

Prova-se que P ≠ NP, mostrando-se 2 problemas que são executados em tempo de complexidade constante O(1) em um algoritmo não determinístico, mas em tempo de complexidade exponencial em relação ao tamanho da entrada num algoritmo deterministístico. Os algoritmos são essencialmente simples para que tenham ainda alguma redução significativa em sua complexidade, o que poderia invalidar as provas aqui apresentadas.
Category: Data Structures and Algorithms

[4] viXra:1603.0072 [pdf] submitted on 2016-03-04 18:32:49

Two Problems Proving P <> NP

Authors: Valdir Monteiro dos Santos Godoi
Comments: 7 Pages. Article written around 5 years ago. See also viXra 1603.0107: "Languages Varying in Time and the Problem P x NP".

Is proved that P ≠ NP, showing 2 problems that are executed in constant complexity time O(1) in a nondeterministic algorithm, but in exponential complexity time related to the length of the input (input size) in a deterministic algorithm. These algorithms are essentially simple, so they can not have a significant reduction in its complexity, what could cause the proofs shown here to become invalid.
Category: Data Structures and Algorithms

[3] viXra:1603.0071 [pdf] submitted on 2016-03-04 18:45:49

Dois Problemas Provando P <> NP - v2

Authors: Valdir Monteiro dos Santos Godoi
Comments: 7 Pages. Article written around 5 years ago. It is an enhancement over version 1. See also viXra 1603.0107: "Languages Varying in Time and the Problem P x NP".

Prova-se que P ≠ NP, mostrando-se 2 problemas que são executados em tempo de complexidade constante O(1) em um algoritmo não determinístico, mas em tempo de complexidade exponencial em relação ao tamanho da entrada num algoritmo deterministístico. Os algoritmos são essencialmente simples para que tenham ainda alguma redução significativa em sua complexidade, o que poderia invalidar as provas aqui apresentadas.
Category: Data Structures and Algorithms

[2] viXra:1603.0070 [pdf] replaced on 2016-03-05 21:50:57

Dois Problemas Provando P <> NP - v3

Authors: Valdir Monteiro dos Santos Godoi
Comments: 10 Pages.

Prova-se que P ≠ NP, mostrando-se 2 problemas que são executados em tempo de complexidade polinomial em um algoritmo não determinístico, mas em tempo de complexidade exponencial em relação ao tamanho da entrada num algoritmo deterministístico. Os algoritmos são essencialmente simples para que tenham ainda alguma redução significativa em sua complexidade, o que poderia invalidar as provas aqui apresentadas.
Category: Data Structures and Algorithms

[1] viXra:1603.0069 [pdf] replaced on 2016-03-07 10:35:28

Dois Problemas Provando P <> NP - v4

Authors: Valdir Monteiro dos Santos Godoi
Comments: 11 Pages.

Prova-se que P ≠ NP, mostrando-se 2 problemas que são executados em tempo de complexidade polinomial em um algoritmo não determinístico, mas em tempo de complexidade exponencial em relação ao tamanho da entrada num algoritmo deterministístico. Os algoritmos são essencialmente simples para que tenham ainda alguma redução significativa em sua complexidade, o que poderia invalidar as provas aqui apresentadas.
Category: Data Structures and Algorithms