On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

Parallel parsing of programming languages

A new method of specifying the syntax of programming languages, known as hierarchical language specifications (HLS), is proposed. Efficient parallel algorithms for parsing languages generated by HLS are presented. These algorithms run on an exclusive-read exclusive-write parallel random-access machine. They require O(n) processors and O(log2n) time, where n is the length of the string to be parsed. The most important feature of these algorithms is that they do not use a stack.

Univariate, bivariate, and multivariate methods in corpus-based lexicography : A study of synonymy

In this dissertation, I present an overall methodological framework for studying linguistic alternations, focusing specifically on lexical variation in denoting a single meaning, that is, synonymy. As the practical example, I employ the synonymous set of the four most common Finnish verbs denoting THINK, namely ajatella, miettiä, pohtia and harkita ‘think, reflect, ponder, consider’. As a continuation to previous work, I describe in considerable detail the extension of statistical methods from dichotomous linguistic settings (e.g., Gries 2003; Bresnan et al. 2007) to polytomous ones, that is, concerning more than two possible alternative outcomes. The applied statistical methods are arranged into a succession of stages with increasing complexity, proceeding from univariate via bivariate to multivariate techniques in the end. As the central multivariate method, I argue for the use of polytomous logistic regression and demonstrate its practical implementation to the studied phenomenon, thus extending the work by Bresnan et al. (2007), who applied simple (binary) logistic regression to a dichotomous structural alternation in English. The results of the various statistical analyses confirm that a wide range of contextual features across different categories are indeed associated with the use and selection of the selected think lexemes; however, a substantial part of these features are not exemplified in current Finnish lexicographical descriptions. The multivariate analysis results indicate that the semantic classifications of syntactic argument types are on the average the most distinctive feature category, followed by overall semantic characterizations of the verb chains, and then syntactic argument types alone, with morphological features pertaining to the verb chain and extra-linguistic features relegated to the last position. In terms of overall performance of the multivariate analysis and modeling, the prediction accuracy seems to reach a ceiling at a Recall rate of roughly two-thirds of the sentences in the research corpus. The analysis of these results suggests a limit to what can be explained and determined within the immediate sentential context and applying the conventional descriptive and analytical apparatus based on currently available linguistic theories and models. The results also support Bresnan’s (2007) and others’ (e.g., Bod et al. 2003) probabilistic view of the relationship between linguistic usage and the underlying linguistic system, in which only a minority of linguistic choices are categorical, given the known context – represented as a feature cluster – that can be analytically grasped and identified. Instead, most contexts exhibit degrees of variation as to their outcomes, resulting in proportionate choices over longer stretches of usage in texts or speech.

Grammar and disciplinary culture : a corpus-based study

The present study provides a usage-based account of how three grammatical structures, declarative content clauses, interrogative content clause and as-predicative constructions, are used in academic research articles. These structures may be used in both knowledge claims and citations, and they often express evaluative meanings. Using the methodology of quantitative corpus linguistics, I investigate how the culture of the academic discipline influences the way in which these constructions are used in research articles. The study compares the rates of occurrence of these grammatical structures and investigates their co-occurrence patterns in articles representing four different disciplines (medicine, physics, law, and literary criticism). The analysis is based on a purpose-built 2-million-word corpus, which has been part-of-speech tagged. The analysis demonstrates that the use of these grammatical structures varies between disciplines, and further shows that the differences observed in the corpus data are linked with differences in the nature of knowledge and the patterns of enquiry. The constructions in focus tend to be more frequently used in the soft disciplines, law and literary criticism, where their co-occurrence patterns are also more varied. This reflects both the greater variety of topics discussed in these disciplines, and the higher frequency of references to statements made by other researchers. Knowledge-building in the soft fields normally requires a careful contextualisation of the arguments, giving rise to statements reporting earlier research employing the constructions in focus. In contrast, knowledgebuilding in the hard fields is typically a cumulative process, based on agreed-upon methods of analysis. This characteristic is reflected in the structure and contents of research reports, which offer fewer opportunities for using these constructions.

Between Herbals et alia: Intertextuality in Medieval English Herbals

This study reports a corpus-based study of medieval English herbals, which are texts conveying information on medicinal plants. Herbals belong to the medieval medical register. The study charts intertextual parallels within the medieval genre, and between herbals and other contemporary medical texts. It seeks to answer questions where and how herbal texts are linked to each other, and to other medical writing. The theoretical framework of the study draws on intertextuality and genre studies, manuscript studies, corpus linguistics, and multi-dimensional text analysis. The method combines qualitative and quantitative analyses of textual material from three historical special-language corpora of Middle and Early Modern English, one of which was compiled for the purposes of this study. The text material contains over 800,000 words of medical texts. The time span of the material is from c. 1330 to 1550. Text material is retrieved from the corpora by using plant name lists as search criteria. The raw data is filtered through qualitative analysis which produces input for the quantitative analysis, multi-dimensional scaling (MDS). In MDS, the textual space that parallel text passages form is observed, and the observations are explained by a qualitative analysis. This study concentrates on evidence of material and structural intertextuality. The analysis shows patterns of affinity between the texts of the herbal genre, and between herbals and other texts in the medical register. Herbals are most closely linked with recipe collections and regimens of health: they comprise over 95 per cent of the intertextual links between herbals and other medical writing. Links to surgical texts, or to specialised medical texts are very few. This can be explained by the history of the herbal genre: as herbals carry information on medical ingredients, herbs, they are relevant for genres that are related to pharmacological therapy. Conversely, herbals draw material from recipe collections in order to illustrate the medicinal properties of the herbs they describe. The study points out the close relationship between medical recipes and recipe-like passages in herbals (recipe paraphrases). The examples of recipe paraphrases show that they may have been perceived as indirect instruction. Keywords: medieval herbals, early English medicine, corpus linguistics, intertextuality, manuscript studies

Modality as portrayed in upper secondary school textbooks : A corpus-based approach

Tämän pro gradu -lopputyön aiheena on englannin kielen modaalisten apuverbien ns. ydinjoukko: will, would, can, could, shall, should, may, might ja must. Semantiikan kannalta nämä apuverbit ovat erityisen kompleksisia: niiden tulkinnassa on usein huomattavaa monivivahteisuutta, vaikka perinteiset kieliopit antavat ymmärtää niillä olevan kaksi tai kolme toisistaan selkeästi erillään olevaa merkitystä. Ne asettavatkin vieraan kielen oppimisympäristössä erityisiä haasteita. Viimeaikainen kehitys korpuslingvistiikan metodeissa on tuottanut entistä tarkempia kuvauksia siitä, miten modaalisia apuverbejä nykyenglannissa käytetään ja mihin suuntaan niiden kehitys on lyhyenkin ajan sisällä kulkenut. Tämän tutkielman tavoitteena on ollut verrata näiden uusien tutkimusten tuloksia siihen todellisuuteen, jonka englannin kielen lukiotasoinen oppimateriaali Suomessa opiskelijalle tarjoaa. Lähdin siitä, että opetussuunnitelman vaatima autenttisuus ja kommunikaativisuus kieltenopetuksessa tulisi näkyä tasapuolisena modaalisten apuverbien kohteluna. Alkuperäinen hypoteesini kuitenkin oli, että siinä miten modaalisuus ilmenee autenttisessa ympäristössä ja siinä miten se esitetään oppikirjoissa, on poikkeavuuksia. Lähestymistapani tähän tutkielmaan oli korpuslähtöinen. Valitsin kahdesta lukion kirjasarjasta ne kirjat, joissa modaaliset apuverbit mainittiin eksplisiittisesti. Skannasin jokaisen neljästä eri kirjasta löytyvän (kokonaisen) tekstin ja rakensin näistä aineksista pienen korpuksen. Tästä korpuksesta hain korpusanalyyseihin tarkoitetulla ohjelmalla kaikki lauseet, joissa esiintyi modaalisia apuverbejä. Tämän jälkeen analysoin jokaisen modaalisen apuverbin semanttisesti lauseyhteydessään. Tämän analyysin tuloksena pystyin rakentamaan taulukoita ja vertailemaan tuloksia uusimpien tutkimusten tuloksiin. Tämän tutkielman perusteella poikkeavuuksia on olemassa. Yleisesti ottaen modaalisten apuverbien keskinäinen frekvenssi oli oikean suuntainen: mitään apuverbiä ei ollut käytetty merkittävästi enemmän tai vähemmän kuin mitä viimeaikaisen tutkimuksen valossa olisi suotavaa. Sen sijaan apuverbien semanttisessa jakaumassa oli paikoin suuriakin eroja siinä, mitkä merkitykset oppikirjoissa painottuivat ja mitkä taas nykyenglannissa vaikuttaisivat olevan frekvensseiltään suurempia. Erityisesti can ja must erottuivat joukosta siinä, että oppikirjojen tarjoama kuva niiden käytöstä on päinvastainen kuin mitä voisi odottaa: can-verbin käyttö painottui selvästi tarkoittamaan ’kykyä’ eikä ’mahdollisuutta’, joka nykytutkimuksen valossa on sen pääasiallinen käyttötapa. Toisaalta must tarkoitti aineistossa ylikorostuneesti ’pakkoa’, kun se useimmiten nykyään tarkoittaa yhtä usein ’johtopäätöstä’ kuin ’pakkoa’. Lisäksi ’lupaa’ pyydettiin aineistossa merkillisen harvoin. Tulosten perusteella esitän, että oppikirjojen tekijät yleisellä tasolla luopuisivat kielioppikirjojen luutuneista käsityksistä ja uskaltaisivat altistaa opiskelijat koko modaalisten apuverbien merkityskirjolle.

The SCOTS corpus and TEFL: Discovering and Using Strategies of Spoken English in Finnish Upper Secondary Schools

Suomen koulutuspolitiikasta vastaavat viranomaiset ovat reagoineet kansainvälisten kommunikaatiotarpeiden asettamiin haasteisiin ja muuttaneet yhden lukion A-tasoisen vieraan kielen kurssin sisällön vastaamaan suullisen viestinnän tarpeita. Tutkimuksessa selvitetään, miten englannin puhestrategioita voi opettaa suomalaisille lukiolaisille ja mitä metodeja on käytettävissä puhestrategioiden oppimisen arvioimiseksi. Vastaan asettamiini kysymyksiin aikaisemman tutkimuskirjallisuuden ja englannin kielen lukio-opetuksesta keräämäni aineiston avulla. Keskeisiä elementtejä tutkielmassa ovat erityisesti pragmaattinen kompetenssi ja kolme yleisen tason puhestrategiaa (keskustelun aloittaminen, oman puheenvuoron säilyttäminen sekä keskustelun ylläpitäminen). Aineistossa on mukana 65 ensimmäisen vuosiluokan lukiolaista (luokka A ja B) Helsingistä ja Espoosta. Opetusmateriaalina on käytetty SCOTS korpusta; tarkemmin määriteltynä puhetiedosto nimeltä Conversation 20: Four secondary school girls in the North East. Tiedostossa esille tulleet, kolmeen puhestrategiaan liittyvät fraasit, sanat ja rakenteet havainnollistettiin opiskelijoille mm. AntConc - konkordanssiohjelman avulla. Opiskelijat tekivät myös kirjallisia ja suullisia harjoituksia, jotka liittyivät puhestrategioihin. Neljälle vapaaehtoiselle opiskelijalle suunnattu toinen suullinen tehtävätyyppi vapaamuotoisine keskusteluineen äänitettiin, transkriboitiin ja tuloksia arvioitiin mm. eurooppalaisen viitekehyksen avulla. Lisäksi B - luokka vastasi kyselylomakkeeseen, jossa kysyttiin heidän mielipiteitään esim. hyödyllisimmästä testioppitunnista sekä heidän osallistumishalukkuudestaan uudelle pitkän englannin kahdeksannelle syventävälle kurssille. Tutkimustulokset ovat kannustavia ja osoittavat, että puhestrategioita on mahdollista opettaa jo lukiotasolla. Vaikka tutkimuksessa käytetty lähestymistapa oli opiskelijoille osittain uusi, valtaosa heistä myönsi oppineensa uutta englannin kielen keskustelurakenteista. Lisäksi vapaaehtoisten opiskelijoiden äänitetyt ja transkriboidut keskustelut tarjoavat hyvän lähtökohdan mahdolliselle jatkotutkimukselle.

SHAMP: An experimental shared memory multimicroprocessor system for performance evaluation of parallel algorithms

In this paper, the design and implementation of a single shared bus, shared memory multiprocessing system using Intel's single board computers is presented. The hardware configuration and the operating system developed to execute the parallel algorithms are discussed. The performance evaluation studies carried out on Image are outlined.

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log2n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.

A new algorithm for parallel solution of linear equations

Abstract is not available.

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.

Note On The Stability Of Parallel Magnetic-Fields - Comment

It is shown that the conclusions arrived at regarding the instability of an incompressible fluid cylinder in the presence of the magnetic field and the streaming velocity in a recent communication easily follow from the study of propagation characteristics of Alfvén surface waves along cylindrical plasma columns made earlier.

Topochemical dimerization of non-parallel double bonds: 7-methoxycoumarin

X-ray crystal structure analysis of 7-methoxycoumarin reveals that the reactive double bonds are rotated by about 65° with respect to each other, the centre-to-centre distance between the double bonds being 3.83 Å. In spite of this unfavourable arrangement, photodimerization occurs in the crystalline state yielding the syn-head-tail dimer as the only product. Lattice energy calculations on ground-state molecules in crystals throw light on the mechanism of the reaction.

Implementation of parallel tridiagonal solvers for a heterogeneous computing environment

Tridiagonal diagonally dominant linear systems arise in many scientific and engineering applications. The standard Thomas algorithm for solving such systems is inherently serial forming a bottleneck in computation. Algorithms such as cyclic reduction and SPIKE reduce a single large tridiagonal system into multiple small independent systems which can be solved in parallel. We have developed portable cyclic reduction and SPIKE algorithm OpenCL implementations with the intent to target a range of co-processors in a heterogeneous computing environment including Field Programmable Gate Arrays (FPGAs), Graphics Processing Units (GPUs) and other multi-core processors. In this paper, we evaluate these designs in the context of solver performance, resource efficiency and numerical accuracy.