« iepriekšējāTurpināt »
VARIOUS COMPUTING ACTIVITIES
The International Symposium on Algorithms '91 and visits to
Computing in Taiwan are summarized.
by David K. Kahaner
world-wide recession. The savings rate Since 1990 Taiwanese companies BACKGROUND
has been hovering slightly over 30%. have invested more than $400M in the
Since 1971 the country's gross national Bay area of northern California. Billions I first visited Taiwan, Republic of product has gone from $6.6B to $180B. more have been invested in Southeast China (ROC), in December of 1990 Europe is a huge trading partner, too: Asia; in 1990 Taiwan became Malaysia's (see my report “Computing in Taiwan," $14B in 1991, with a trade surplus of number one investor, $2.3B in that Scientific Information Bulletin 16(2), over $4B. In addition to trade with the year. More than $500M has been invested 23-29 (1991)]. The current report pro- West, there is a growing volume of in Vietnam since it was opened to outside vides updates and further perspective. trade with mainland China, up nearly investors several years ago. In addition, At the time of my first visit I com- 50% last year (1991). So-called cross- there has been major Taiwan investmented on the lack of applications Strait trade was more than $4B for the ment in Mexico, anticipating the open research. I still sense something of a first 10 months of 1991. Recently there border to the United States. disconnect between what appears to
have also been calls for a loose ecobe very high quality academic research nomic community between Taiwan, INTERNATIONAL SYMPOSIUM and industrial needs. However, in the Hong Kong, and the coastal provinces ON ALGORITHMS '91 (ISA'91) area of computing, the soon-to-be- of southern mainland China, perhaps opened National Center for High Per- even including Singapore.
Almost 140 scientists met at the formance Computing will go a long A government-backed consortium Academia Sinica, in Taipei, Taiwan, way towards bringing research and led by the Taiwan Aerospace Corpora- 16-18 December 1991 for the Second development (R&D) closer together. tion (TAC) has proposed to purchase International Symposium on Algo
Please refer to the earlier report 40% of McDonnell Douglas' commer- rithms. ISA'91 was organized by the for general background on Taiwan. cial jetliner operations for about $2B, Institute of Information Science, Suffice to say that Taiwan's 20+ millions and the deal will go through in January Academia Sinica, and National Tsing are enjoying a remarkable period of if the U.S. and ROC Governments agree. Hua University, with cooperation from economic growth. The country's for- Purchase of such a large and important the Special Interest Group on Algoeign exchange reserves including gold industry would have a significant impactrithms (SIGAL) of the Japan Informaexceed $90B (greater than Japan's) and on Taiwan's industrial base and would tion Processing Society. The first sympoare projected to go beyond $100B in certainly require heavy supercomput- sium was held last year (1990) in Japan 1992, driven in large part by a trade ing usage. In a related matter, a recent as SIGAL International Symposium surplus of about $13B in 1991. Per announcement in a Taipei paper asked on Algorithms. The participant distribucapita income, $8,800 (third highest in for a bid on supersonic wind tunnel tion was approximately as follows. Asia behind Japan and Hong Kong), is measurement systems. The country growing about 9% annually, as is gen- already has at least one supercomputer eral economic growth in spite of the and several dozens of U.S. mini-supers.
No. counting, enumerating, or selecting is that contributed. There really wasn't a
significant. A typical one is to design “ringer” in the bunch. Taiwan
the wiring path in VLSI to minimize From the Asian side, my own favorU.S.
space, crossovers, etc. Although a few ite papers were as follows. Japan
papers dealt with parallel or distribHong Kong
uted algorithms, these were in the • Inagaki (Nagoya, Japan) et al. on Germany 6 minority.
constructing shortest watchman Sweden
Although potential applications routes in a polygon. The watchman Canada
abound, ISA papers actually empha- route problem deals with finding China
sized theoretical aspects. Coming from the shortest route from a point back Singapore
a mathematics background, I felt right to itself, so that every point in the India
at home with the tone of the papers, polygon can be seen from at least Australia
although the techniques used were quite one point along the route.
different from those I was familiar Included in these numbers are several with. Most papers presented elegant • Ho (Academia Sinica, Taiwan) on Taiwan-born scientists, now working theorems analyzing discrete algorithms, three-dimensional channel routing in the United States.
data structures, or generalized graphs (for VLSI), which tries to minimize I was pleasantly surprised to dis- and expressed results as “order” or other the number of “vias," connections cover that the conference organizers limiting relations. Here is a typical between different levels of the had not only issued a Proceedings but definition: “We call such an algorithm configuration. had arranged for Springer-Verlag to competitive' if its cost performance is publish this as part of their Lecture at most a constant multiple of the ideal • Chan (Hong Kong) et al. on path Notes in Computer Science. Very careful cost.” There was very little evidence of algorithms for robots minimizing advance planning permitted all but the actually using a computer, except per- total distance traversed. This was invited papers to be included in this haps to experiment as a way of suggest- one of a series of very excellent papers book. For those, readers can contacting direction, or verify an analysis. on geometry. the individual authors.
Although the subject is different, this is
analogous to the style in some theoret- • Ibaraki (Kyoto, Japan) et al. on a ISA'91 Algorithms
ical numerical analysis papers. That problem with application to the Springer Lecture Notes in
kind of analysis can ultimately be impor- testing of logic circuits by applyinga Computer Science #557 tant, although research has been much (limited) selected set of test inputs. W.L. Hsu, R.C.T. Lee (editors) 1991 more practically oriented.
Of course, one wants to make correct
To succeed in such research it is decisions with minimum testing. Because of the wide distribution of this only necessary to have capable book, I will only make a few general scientists--equipment and other expen- • Chan (Hong Kong) et al. on how to comments about the papers at this sive facilities are secondary. Of course, make use of a hypercube computer symposium
this is one reason that ill-equipped that has some faulty nodes to run an The goal of the ISA is to promote a research institutes sometimes concen- algorithm requiring a full binary tree. forum for Pacific Rim researchers as trate in these areas (not the case for the I was impressed last year with related well as those in other parts of the world host institution). Thus it is not surpris- work from these authors (see my to exchange ideas on computing theory. ing that there is an almost seamless
earlier report). The last two words here are important flow of research results moving around in the context of this symposium. While the world in this field. There appeared For additional details about ISA'91 “algorithms” has a wide variety of to be a great deal of cross fertilization, contact meanings, ISA participants are con- including students of Western sciencerned almost exclusively with discrete tists graduating and establishing posi- Prof. R.C.T. Lee algorithms. The papers focused on tions in other countries. It did seem Dean of Academic Affairs sorting, permuting, the discrete aspects that many of the key directions were National Tsing Hua University of computational geometry, combina- set by Western papers. But the level of Hsinchu, Taiwan 30043, ROC torial optimization, graph traversal, etc. sophistication in almost all the papers
Tel: +886-35-719134 (0) Such algorithms have applications in was very high, and I spotted excellent Fax: +886-35-722713 virtually any problem area in which work from just about every country E-mail: email@example.com
Physics Department at the State Uni- Dr. Wu explained to me that in
versity of New York at Buffalo. He has Taiwan responsibility for development The ISA'91 symposium, described had a pivotal rule in the development of science and technology is divided in above, was held in the Academic Activ- of science in Taiwan since the mid- three: the Ministry of Defense has its ity Center of the Taiwan Academia 1950s and has been President of the own budget and research agenda and is Sinica (Academy of Science). Academia Academia since 1983. He was mostly responsible for technologies related to Sinica was founded in 1928 on the responsible for the science develop- military needs; the Ministry of Economic mainland and then moved to Taiwan in ment program that sent thousands of Affairs for various research institutes 1949. The Academia has two basic Taiwanese abroad to study and even- and science and technology related to missions: conducting scientific research tually to return and staff the country's industrial development; and the and coordinating scientific activities of universities and research institutes. National Science Council (NSC) for other government research institutes Another of his proposals was to limit all academic programs relating to basic, and universities. The 19 institutes at all academic administrative appoint- applied, and social science. Academia the Academia are shown in Table 1. ments to a once-renewable 3-year term. Sinica is somewhat special, as it belongs
The older institutes were established A recent public opinion poll showed directly to the Presidential House first on the Chinese mainland, although that he was one of the two most popu- (Taiwan's White House). As Academia only 2, Mathematics and History and lar men in the country. In 1984 he won president, Wu reports directly to Philology, were moved to Taiwan intact; the Magsaysay Award, roughly the Asian
the Magsaysay Award, roughly the Asian Taiwan's President; thus his voice is for 11 others personnel and equipment equivalent of the Nobel Prize. In May loudly heard. The current Academia were left behind. Several years before 1991 he and U.S. President Bush received
1991 he and U.S. President Bush received budget is on the order of $30M annually. an institute is officially established, a honorary Ph.D. degrees from Michigan, President Wuspoke strongly about the preparatory office is first set up (denoted and Wu has a wonderful photo on his distinction between basic (fundamenby "pre" in Table 1). At the beginning wall commemorating this event. tal) research and other approaches; it these offices are mostly planning, but
is clear that he favors and has strongly eventually become full fledged research
supported the former. facilities. Note that not all institutes count administrative staff in the figures given in Table 1, so numbers are
Table 1. The Various Institutes of Academia Sinica
Staff told that the total staffing is well over
Established 1,000, although it fluctuates because of Physics
72 part-time employment. Chemistry
79 I was fortunate to be able to have a History & Philology
103 lengthy conversation with Mathematics
33 Dr. Ta-you Wu Modern History
58 President, Academia Sinica Economics
55 Taipei, Taiwan, ROC Zoology
36 American Culture
46 Dr. Wu, 84, was trained as a physicist Biological Chemistry
1981 Social Sciences & Philosophy
69 with a Ph.D. from Michigan and pubEarth Science
1982 lished his first book, Vibrational SpecInformation Science
70 tra and Structure of Polyatomic MoleComputing Center
NA cules, in 1938. After World War II he Statistical Science
1987 headed the Theoretical Physics SecBiomedical Science
251 Atomic & Molecular Science tion of Canada's National Research
pre 1982 Molecular Biology
133 Council and later was Chairman of the Chinese Literature & Philosophy
Nevertheless, all is not perfect. The This is related to architecture design, by the research faculty with very few original intention of the Academia Sinica compilers, and parallelizing various con- administrative duties. It is a research was that it would serve as consultant to structions within existing languages. institution. There are no teaching duties the President on academic related There does not appear to be any signif- because there are no students; instead, matters. However, I was told that in the icant research in numerical methods, research is supported by many full-time past this function was rarely used, and either theory or implementation. There assistants. Many faculty do, however, they have become another (large) is interesting robotics research related offer courses in nearby universities, research institute. Staff can submit to dexterous manipulation, coordinated
to dexterous manipulation, coordinated and there are the usual seminars, conresearch proposals to NSC for funding motion of multiple robot arms, and ferences, etc. Many IIS staff were heavily support just like any university faculty, simulation. As the ISA symposium occupied with the ISA symposium and but they cannot admit students and do would suggest, there are about a half there wasn't much other activity while not perform any instructional function. dozen people working on the theoret- I was there. I did not visit the Institute Many Taiwan scientists feel that the ical aspects of discrete (combinatoric) of Mathematics, but the printed materesources being devoted to the algorithm development. Finally, there rials that I was given discuss work in Academia's research program should are significant efforts in the areas of rank inequalities for chordal graphs, be re-oriented toward directly assisting real-time operating systems, high-speed probability, algebra, and number theory. the country's industrial infrastructure. networking, software methodologies, There does not appear to be any signifIn the area of computing, similar views and a small effort VLSI layout design. icant activity in numerical analysis. A have been expressed by Taiwan-born, A new eight-story building is being quarterly Bulletin of the Institute of U.S.-based scientists, who feel that much built to be finished before 1994, suffi- Mathematics has been published for more emphasis needs to be placed on cient to house more than 50 Ph.D. almost 20 years, and since 1976 another practical systems-building experiences researchers. The institute publishes an quarterly, Mathmedia, for less esoteric and less on highly theoretical paper English language research journal, articles. studies. My own opinion is that it would Journal of Information Science and With nearly 1,000 scientists in so be healthy to better tie R&D done at Engineering, which contains articles from many disciplines, Academia institutes the Academia to that supported by other Taiwanese researchers (not primarily are individually worth serious examiministries, as these seem more aligned those at IIS). Electronic access has nation. The preceding comments are with the country's needs.
recently been expanded to Internet meant to provide background and The ISA symposium was sponsored service, allowing file transfer, Telnet, overview material only. by the Institute of Information Science etc. While Chinese is the daily working (IIS). There were informal opportuni- language, almost all IIS scientists can NATIONAL CENTER FOR ties to visit its building, but no chance function adequately in English. Many HIGH PERFORMANCE to see any other institutes. Computing have spent substantial time in the West, COMPUTING facilities were comparable to well- and a few speak excellent colloquial equipped Western laboratories: an English. Information about this institute In December 1990 I reported on the N-cube, two Iris graphics and about 50 generally, or the journal in particular, plans for a national supercomputer other Unix workstations, and plenty of can be obtained from the following. center in Taiwan. Almost 1 year later I PCs. There is access to an ETA-10,
decided to see how things were coming which is run by the Computing Center. Prof. Lin-Shan Lee
along. I met with There is a computer vision laboratory Institute of Information Science with image scanners, camera, image Academia Sinica
Prof. San-Cheng Chang processors to support two-dimensional Taipei, Taiwan 115, ROC
Director, National Center animation and three-dimensional visu- Tel: +886-2-788-3799
for High Performance alization work, stereo vision, and neural Fax: +886-2-782-4814
Computing (NCHC) network research. There is a long-term E-mail: firstname.lastname@example.org
P.O. Box 23-115 project in natural language under
Taipei, Taiwan, ROC standing for Mandarin Chinese. The I was told that the Institute of Infor- Tel: +886-2-3630231 X2189 N-cube gives some opportunity to mation Science is typical of those at Fax: +886-2-3661571 perform parallel processing research. Academia Sinica. It is essentially run E-mail: email@example.com.
Also at the same address is Dr. down the park's walls (and eliminating NCHC is to be hooked up to a local Kuo-Wei Wu, who was on leave from tenants' tax breaks) to integrate its network (FMAN) within Hsinchu's Cray Research to help with NCHC's companies better into the society and industrial park. In addition, it will be planning. He has now resigned from also setting up similar parks in other hooked to TANET (Taiwan Academic Cray and is a Deputy Director of NCHC. parts of the country such as Kaohsiung. Network), a T1-based public network (Ayear earlier Wu had explained some Nevertheless, HSIP is a must-stop for sponsored by the Ministry of Education of Taiwan's goals in the area of super- anyone interested in industrial devel- and part of Internet. In addition, there computing.) Chang, Wu, and a good- opment in Taiwan.
will be long-haul T1- or T3-based sized administrative staff are currently Taiwan is certainly not the first dedicated lines set up to major univerhoused at National Taiwan University, country in Asia to build a nationally sities and research institutes that need in the city of Taipei. However, a accessible supercomputer center, but such access. NCHC will be internally 15,000 m2 building is almost complete. it hopes to benefit from experiences in networked with the Fiber Distribution This is in Hsinchu Science-Based other places. Planning took place over Data Interface (FDDI). Industrial Park (HSIP), 70 km south of 4 years and NCHC is organizationally Chang and Wu emphasized to me Taipei, the and site of two major national placed under the National Science that one of NCHC's major functions is universities, National Tsing Hua (with Council and will be a national labora- to provide expertise. They expect 1,200 about 4,500 students and about 450 tory there. It is expected that in late potential users during 1992. This will faculty) and National Chiao-Tung 1992, when the facility finally opens, it have to be all in the last third of the University. Hsinchu's model seems to will serve both the academic as well as year, as the hardware is not scheduled be Tsukuba Science City in Japan; there the industrial community. The empha- to come on line until late summer. By are also somewhat similar places in sis is to be on application expertise. 1995 they are hoping to support at least Korea, Singapore, etc. It is usually NCHC is operated in 5-year phases, 2,000 users. Major applications are referred to as Taiwan's “Silicon Valley I” the first ending in June 1995. This expected to be molecular modeling,
I did not visit the park this year but phase was budgeted with $89M, about computational fluid dynamics, elechad been in Hsinchu a year earlier and half for computer-related hardware and tron device simulation, structural wrote about it then. On a site of nearly software systems. NCHC's director is analysis, atmospheric science, and 1,000 acres there are about 150 fac- chosen by NSC from relevant university earthquake wave studies. They are tories. An additional 500 acres have faculty. Under him are five divisions. anticipating the usual bevy of academic been obtained and plans are to house
exchanges, newsletters, seminars, etc., another 150 companies within 5 years. • Administration
not only focused on how best to deal Presently, production values (%) of • Operation
with existing applications on NCHC's companies in the park are as follows. • Hardware/Software Management equipment but also anticipating new • Research/Development
computing environments such as highly Computers and peripherals 49.0 • Education/Promotion
parallel computers that will become Integrated circuits 30.0
user-practical in the future. Telecommunications equipment 17.0 The last two distinguish NCHC from a At this date a final selection of Opto-electronic equipment
1.7 pure cycle-shop and make it more like hardware has not yet been made. The Miscellaneous.
2.3 one of the National Science Founda- expected vendors have all submitted
tion (NSF) Centers in the United States. proposals and these are now being HSIP, like other commercially based In addition, special interdisciplinary evaluated. The specifications call for a high-tech industrial parks with many laboratories and projects will be high-performance computing engine, tenants, has some ailing companies, established as needed. Current plans a front-end system, and a large number some with products that are less high- are for a scientific visualization labora
are for a scientific visualization labora- of workstations for visualizations, comtech than authorities might want (one tory, and projects in molecular model- puting, and software development. The company wanted to develop robotsing and public domain mathematical supercomputing engine will be installed and is now engaged in making window- library development, and these are to in two stages, 1992 and 1994, to ensure washing machines), and some whose be integrated within and across the that new equipment will be installed as high-tech 3 years ago is now just labor divisions. Staff will be about 100, simi- it becomes available. saving. There is talk both about tearing lar in scale to the NSF Centers.