On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

Hebreu: llengua, literatura, gramàtica [versió html]

El llibre Hebreu: llengua, literatura i gramàtica conté una síntesi breu de la història de la llengua hebrea, un resum de la història de la literatura escrita en hebreu i una descripció panoràmica dels trets gramaticals més significatius de la llengua hebrea contemporània. Aquestes pàgines han estat pensades per a servir de complement als cursos d'hebreu de la Universitat de Girona

Hebreu bíblic [versió html]

Manual pensat per a servir de guia per als alumnes dels curs Hebreu Bíblic de la Universitat de Girona. Hebreu Bíblic conté una descripció de la gramàtica fonamental de la llengua hebrea bíblica en 54 lliçons. Cada lliçó presenta sols els continguts essencials de la gramàtica, que en el treball de classe és ampliat i matisat. La segona part del manual consta de 24 vocabularis i exercicis formats exclusivament per frases tretes del text de la Bíblia