Reading PAGE

Peer Evaluation activity

Trusted by 1
Reviews 1
Downloads 15353
Views 63
Full text requests 3
Followed by 1
Following... 3
Funded by 4

Total impact ?

    Send a

    David has...

    Trusted 1
    Reviewed 0
    Emailed 0
    Shared/re-used 0
    Discussed 0
    Invited 0
    Collected 9

    This was brought to you by:

    block this user David M. W. Powers Trusted member

    Professor / David.Powers@flinders.edu.au

    Flinders University, School of Computer Science, Engineering and Mathematics, Adelaide, South Australia
    KUB/Tilburg University, ITK/Institute for Language and Knowledge Technology, Tilburg, Brabant, Holland
    FB Informatik/Faculty of Computer Science, University of Kaiserslautern, Germany
    Telecom Paris/ENST, Paris, France
    Macquarie University, Sydney, NSW, Australia
    UNSW/University of New South Wales, Sydney, NSW, Australia
    Sydney University, Sydney, NSW, Australia
    Cardiff University, Linguistics Department, Cardiff, Wales, UK
    Beijing Municipal Lab for Multimedia & Intelligent Software, Beijing University of Technology, Beijing, China

    Parallel Unification: Practical Complexity

    Export to Mendeley

    Parallel Unification The research discussed in this presentation arises in the context of Parallel Theorem Proving and Logic Programming. These paradigms amount to searching a tree in which a path from root to leaf represents a set of choices, identifying a potential solution. Examining alternative paths in parallel exploits so-called OR-parallelism whilst searching at different levels in parallel amounts to AND-parallelism. In addition, it is possible to parallelize the unification process, or use lazy evaluation involving delayed unification or bookkeeping [8]. Interestingly, unification has proven a problem both for sequential and parallel implementation. The standard unification algorithms used in Prolog systems are not sound, and the straightforward fixes lead to exponential execution time. There are, however, linear and near- linear time sound sequential algorithms. Unfortunately, even the unsound algorithms don’t parallelize well, and exhibit worst case linear performance. This has lead to parallelization of unification being eschewed, although the pathological cases are rare. But unification has usefully been parallelized [1] and the pathological cases have been characterized [8]. Parallel Hardware Theoretical characterization of the complexity of parallel unification and reasoning systems rends to rely implicitly or explicitly on a Parallel RAM (PRAM) model. The quicksort algorithm is a standard Prolog demonstration with expected N logN sequential performance. A simulated parallel reasoning system gave logN performance with its implicit PRAM model and a PRAM algorithm was derived from it [9]. Although there are now several such O(logN) algorithms around (and the derived QuickSort and RadixSort algorithms have amongst the lowest constants), there are actually O(log2N) algorithms which will execute faster in any achievable implementation! Ironically, there are also Ο(1) algorithms [2] which are similarly bad!! The paper will discuss what these orders really mean and the factors which are hidden by the current models of parallelism. Indeed, the serial characterizations also hide many constants and are not truly scalable either! We characterize algorithms in terms of the memory bandwidth or buswidth, w, noting that a general sorting task involving N items will scale only if w >= logN with PRAM or Sequential RAM. With a constant w we can achieve O(wN) bit-level cost giving O(w log2N) bit-level delay [3]. Note that any parallel architecture whose connectivity and bandwidth doesn’t scale as logN will incur (possibly multiple) multiplicative factor(s) of logN.

    Oh la laClose

    Your session has expired but don’t worry, your message
    has been saved.Please log in and we’ll bring you back
    to this page. You’ll just need to click “Send”.

    Your evaluation is of great value to our authors and readers. Many thanks for your time.

    Review Close

    Short review
    Select a comment
    Select a grade
    You and the author
    Anonymity My review is anonymous( Log in  or  Register )
    publish
    Close

    When you're done, click "publish"

    Only blue fields are mandatory.

    Relation to the author*
    Overall Comment*
    Anonymity* My review is anonymous( Log in  or  Register )
     

    Focus & Objectives*

    Have the objectives and the central topic been clearly introduced?

    Novelty & Originality*

    Do you consider this work to be an interesting contribution to knowledge?

    Arrangement, Transition and Logic

    Are the different sections of this work well arranged and distributed?

    Methodology & Results

    Is the author's methodology relevant to both the objectives and the results?

    Data Settings & Figures

    Were tables and figures appropriate and well conceived?

    References and bibliography

    Is this work well documented and has the bibliography been properly established?

    Writing

    Is this work well written, checked and edited?

    Write Your Review (you can paste text as well)
    Please be civil and constructive. Thank you.


    Grade (optional, N/A by default)

    N/A 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10
    Close

    Your mailing list is currently empty.
    It will build up as you send messages
    and links to your peers.

     No one besides you has access to this list.
    Close
    Enter the e-mail addresses of your recipients in the box below.  Note: Peer Evaluation will NOT store these email addresses   log in
    Your recipients

    Your message:

    Your email : Your email address will not be stored or shared with others.

    Your message has been sent.

    Description

    Title : Parallel Unification: Practical Complexity
    Author(s) : David M. W. Powers
    Abstract : Parallel Unification The research discussed in this presentation arises in the context of Parallel Theorem Proving and Logic Programming. These paradigms amount to searching a tree in which a path from root to leaf represents a set of choices, identifying a potential solution. Examining alternative paths in parallel exploits so-called OR-parallelism whilst searching at different levels in parallel amounts to AND-parallelism. In addition, it is possible to parallelize the unification process, or use lazy evaluation involving delayed unification or bookkeeping [8]. Interestingly, unification has proven a problem both for sequential and parallel implementation. The standard unification algorithms used in Prolog systems are not sound, and the straightforward fixes lead to exponential execution time. There are, however, linear and near- linear time sound sequential algorithms. Unfortunately, even the unsound algorithms don’t parallelize well, and exhibit worst case linear performance. This has lead to parallelization of unification being eschewed, although the pathological cases are rare. But unification has usefully been parallelized [1] and the pathological cases have been characterized [8]. Parallel Hardware Theoretical characterization of the complexity of parallel unification and reasoning systems rends to rely implicitly or explicitly on a Parallel RAM (PRAM) model. The quicksort algorithm is a standard Prolog demonstration with expected N logN sequential performance. A simulated parallel reasoning system gave logN performance with its implicit PRAM model and a PRAM algorithm was derived from it [9]. Although there are now several such O(logN) algorithms around (and the derived QuickSort and RadixSort algorithms have amongst the lowest constants), there are actually O(log2N) algorithms which will execute faster in any achievable implementation! Ironically, there are also Ο(1) algorithms [2] which are similarly bad!! The paper will discuss what these orders really mean and the factors which are hidden by the current models of parallelism. Indeed, the serial characterizations also hide many constants and are not truly scalable either! We characterize algorithms in terms of the memory bandwidth or buswidth, w, noting that a general sorting task involving N items will scale only if w >= logN with PRAM or Sequential RAM. With a constant w we can achieve O(wN) bit-level cost giving O(w log2N) bit-level delay [3]. Note that any parallel architecture whose connectivity and bandwidth doesn’t scale as logN will incur (possibly multiple) multiplicative factor(s) of logN.
    Keywords : Parallel Logic Programming, Parallel Sorting

    Subject : Parallel Logic Programming, Sorting Networks, CRCW-PRAM
    Area : Computer Science
    Language : English
    Year : 1995

    Affiliations Flinders University, School of Computer Science, Engineering and Mathematics, Adelaide, South Australia
    Editors : Todd Rockoff
    Conference_title : Australasian Computer Architecture Workshop

    Leave a comment

    This contribution has not been reviewed yet. review?

    You may receive the Trusted member label after :

    • Reviewing 10 uploads, whatever the media type.
    • Being trusted by 10 peers.
    • If you are blocked by 10 peers the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

    Does this seem fair to you? Please make your suggestions.

    Please select an affiliation to sign your evaluation:

    Cancel Evaluation Save

    Please select an affiliation:

    Cancel   Save

    David's Peer Evaluation activity

    Trusted by 1
    Reviews 1
    Downloads 15353
    Views 63
    Full text requests 3
    Followed by 1
    Following... 3
    Funded by 4
    • Australian Speech Science Infrastructure: An Audio-Video Speech Corpus of Australian English, Grant Number LE0989734 / Year 2009
    • From Talking Heads to Thinking Heads: A Research Platform for Human Communication Science , Grant Number TS0669874 / Year 2006
    • Heterodensity neuroimaging techniques for spatiotemporal identification and localization , Grant Number DP0988686 / Year 2009
    • Enhanced brain and muscle signal separation verified by electrical scalp recordings from paralysed awake humans, Grant Number DP110101473 / Year 2011

    David has...

    Trusted 1
    Reviewed 0
    Emailed 0
    Shared/re-used 0
    Discussed 0
    Invited 0
    Collected 9
    Invite this peer to...
    Title
    Start date (dd/mm/aaaa)
    Location
    URL
    Message
    send
    Close

    Full Text request

    Your request will be sent.

    Please enter your email address to be notified
    when this article becomes available

    Your email


     
    Your email address will not be shared or spammed.