Parallelizing Translation

[Walter B. Ligon III]

The problems outlined below are well known, and have been for a good 50
years.  Partial solutions to these problems are many and varied and in all
cases Alan is correct - the correct translation of one sentence depends on
the translation of previous sentences, previous activities, and previous
knowledge about the world.

This, however, has nothing to do with the parallelizability of the algorithms
used to impelement this kind of translation.  There are many, many examples of
algorithms that involve complex dependencies between data values that can
be highly parallelized - especially in the area of language translation.
Lexical analysis, parsing, and searching of semantice knowledge space are
but a few of the most obvious examples.  One need not translate a paragraph
sentence at a time, and a sentence word at a time - but can translate
paragraph at a time - and can even use contextual cues between paragraphs
and between documents while performing the translation using highly parallel
algorithms.

If you read "The Connection Machine" by Hillis you will find this is EXACTLY
the kind of thing he wanted to do with the CM-1 and why he designed it the
way he did.  This is also why that machine was NOT popular for scientific
computing - which lead to the design of the CM-2 and CM-200 which finially
gave way to the CM-5 which was not designed for this kind of processing at
all, but was designed for scientific computing.

This points out the real issue with parallel translation - unless you are
able to take advantage of the kind of things Robert and others have mentioned
(translate to multiple languages or translate multiple documents or multiple
unrelated passages) effective parallel translation APPEARS to be a fine-grain
problem and may not adapt well to a coarse-grain (Beowulf) architecture.

I think the discussion at hand is a fine example of the fact that the every
day parallelization techniques that are used for SO many important problems
are NOT the only techniques out there.  The Beowulf movement has had the
problematic effect that many self-proclaimed experts are simply unaware of
much of the research in parallel computation that has gone on over the last
40 years - thus leading to miunderstanding and sweeping statements that are
not really productive in the long run.

Beowulf is not the untimate answer - and it will not replace all other forms
of parallel computation.  There ARE problems that fit better onto other
architectures.  Those architectures may not make economic sense right now,
thus we may not see much of them for a while, but that does not invalidate
their inherent value.

I am sure I will not put this discussion to rest, but let me assure you,
machine translation IS a highly parallelizable problem, though that does
not mean Beowulf is an effective architecture for parallelizing it.  Before
anyone screams I'm NOT saying Beowulf ISN'T a good platform either.  I have
not seen any hard results either way - but I can see where it might be a
problem.

Walt

> The distinction I wanted to make was between two
> kinds of situations.
> 
> The first is when you can organize the individual calculation
> goals as an oriented graph with no cycles. As you are all
> aware, this can be parallelized either running concurrent
> processes through separate CPUs, or serially dependent
> processes through a pipeline, or a mix thereof.
> 
> This means that, as Robert Brown pointed out, you can 
> parallelize at (goal =book) level, and probably also at 
> (goal = paragraph) level - though I would have some doubts 
> on this latter for a badly written text! :-(
> 
> But what about each individual paragraph? Many paragraphs 
> belong to the second kind of situation: when the graph 
> has cycles. Maybe an example would help. Say we have three 
> consecutive sentences in a paragraph:
> 
> A = "He's driving a car."
> B = "It's always a Mercedes."
> C = "John always buys them german."
> 
> Translate these into a language where pronouns carry no 
> gender - such as Chinese. You just knocked out the "He" 
> in A, "It" in B, and obtained something like:
> 
> A = "(he/she) drives car."
> B = "Always is Mercedes."
> C = "always John german buy them."
> 
> I think our Chinese readers will agree this is more or less
> a litteral translation of the Chinese equivalent.
> 
> Now translate them back to a language with gender in both
> singular and plural - such as Spanish.
> 
> To get the gender of "(he/she)" back into A , you need the results of C. 
> To get "them" into C ("los" or "las"?), you need B. 
> To get the gender of "Mercedes" in B ("un" or "una"?), you need to resolve
> A. 
> Circular deadlock.
> 
> Try the same exercise with Sheila and her Suzuki motocycle.
> 
> Any program that treats this problem has a granularity that
> must encompass al least all three sentences together.
> 
> Hope this clarifies my position. If you think the example is
> fanciful - just let me say I have translated worse texts,
> some of them legal and notarized. 
> 
> PS: My current interest in parallel programs is their 
> application to run genetic algorithms. 
> 
> Best regards,
> Alan Ward

-- 
Dr. Walter B. Ligon III
Associate Professor
ECE Department
Clemson University