1. Inicio
  2. Atrás
Título: Static lock allocation
Autores: Halpert, Richard
Fecha: 2008
Publicador: McGill University - MCGILL
Fuente:
Tipo: Electronic Thesis or Dissertation
Tema: Applied Sciences - Computer Science
Descripción: The allocation of lock objects to critical sections in concurrent programs affects both performance and correctness. Traditionally, this allocation is done manually by the programmer. Recent work explores automatic lock allocation, aiming primarily to minimize conflicts and maximize parallelism by allocating locks to individual critical sections. We investigate several modes of lock allocation, using connected components (groups) of interfering critical sections on a critical section interference graph as the basis for allocation decisions. Our allocator uses thread-based side effect analysis which is built from several pluggable component analyses. It benefits from precise points-to and may happen in parallel information. Thread-local object information provides a small improvement over points-to analysis alone. Our framework minimizes the restrictions on input programs, dealing gracefully with nesting and deadlock, and requiring only simple annotations identifying critical sections. Legacy programs using synchronized regions can be processed without alteration. We find that dynamic locks do not broadly improve upon identical allocations of static locks, but allocating several dynamic locks in place of a single static lock can significantly increase parallelism in certain situations. We experiment with a range of small and large Java benchmarks on 1 to 8 processors, and find that a singleton allocation is sufficient for five of our benchmarks, and that a static allocation with Spark points-to analysis is sufficient for another two. Of the other five benchmarks, two require the use of all phases of our analysis, one depends on using the lockset allocation, and two benchmarks proved too complex to be automatically transformed to satisfactory performance.
L'allocation des verrous aux sections critiques des programmes construits avec des processus indépendants affecte la performance et la validité de ces programmes. La littérature récente rapporte des résultats pour l'allocation automatique des verrous. Le but est de minimiser les conflits et de maximiser le parallélisme avec une allocation de verrous aux sections critiques individuelles. Nous étudions plusieurs méthodes d'allocation de verrous, en utilisant des composantes connectés des sections critiques qui interfèrent sur un graphe d'interférence des sections critiques. Notre technique d'allocation utilise une analyse d'effets secondaires qui considère chaque processus indépendant individuellement. Notre analyse d'effets secondaires est construit d'un ensemble d'analyses composantes interchangeable. La technique d'allocation peut profiter d'une analyse des pointeurs précises et d'une analyse «may happen in parallel». Nous avons trouvé que la disponibilité des informations qui sont spécifiques à chaque processus indépendant peut améliorer la qualité des résultats par rapport aux résultats de l'analyse avec seulement l'analyse des pointeurs. Notre système demande des pré-requis minimes des programmes qu'il analyse, peut bien analyser les situations d'emboîtement et d'interblocage, et nécessite seulement quelques annotations simples pour identifier les sections critiques. Les logiciels patrimoniales qui portent des régions synchronisés peuvent être analysés directement. Nous avons trouvé que les verrous dynamiques, en général, ne réussissent pas à améliorer la performance au-dessus de celle des verrous statiques. Par contre, l'allocation de quelques verrous dynamiques au lieu d'un seul verrou statique peut augmenter le parallélisme dans certaines situations. Nous avons évalué notre analyse sur une gamme de programmes pour étudier comparée. Les programmes sont écrits en Java et notre gamme comprend des programmes qui va
Idioma: en