*********************************************************** * International Symposium on Parallel Architectures, * * Algorithms, and Networks (ISPAN'94) * * * * Advance Program * *********************************************************** Program Chair Susumu Horiguchi The 1994 International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN'94) is a forum for scientists, engineers and researchers throughout the world to exchange ideas and research results related to current developments and applications of parallel architectures, algorithms, and networks. The symposium will include invited and contributed papers selected among many papers. Proceedings of ISPAN'94 will be published by IEEE Computer Society Press and will be widely circulated. ******** Invited Talks ******** The following researchers have agreed to give invited talks : Tom Knight (MIT), Richard C.T. Lee (Providence University, Taiwan ROC), G.J. Li (ICT, Chinese Academy of Science, China), Howard J. Siegel (Purdue University), and H. Tanaka (Tokyo University). ******** Location ********* The ISPAN'94 will be held at Ishikawa High-Tech Conference Center on the campus of the Japan Advanced Institute of Science and Technology(JAIST) on December 14-16, 1994. JAIST is the first national graduate school for the advancement of the frontiers of science and technology, and is located on the mountain hills in the town of Tatsunokuchi about 10 miles to the south of downtown Kanazawa city. Kanazawa hosts numerous cultural events around the year. As one of the few well-preserved historical cities, it is often regarded as the hidden gem of Japan. ********* Transportation Guideline ********** Kanazawa is located at the Hokuriku destrict, facing the Sea of Japan, and is about 400km northwest of Tokyo area, 300km northeast of Kyoto and Osaka. You must first go to the Kanazawa station, Komatsu airport by train or airway. By train, it is about 4 hours from Tokyo(by super-express train Shinkansen via Nagaoka). By airway, it is about 1 hour from Tokyo Haneda airport. From Osaka, trains are available from new Osaka International Airport to Kanazawa station. Shuttle bus lines to Kanazawa city are available for each flight. ********** Accomodation ************* The following hotel is available at special symposium rate and will provide shuttle bus lines to the symposium site. Please make reservation directly with the hotels, and identify yourself as an ISPAN'94 attendee. Free shuttle buses from Kanazawa station to the hotel are scheduled. International Hotel Kanazawa Ru 8, Oonuka-cho, Kanazawa, Ishikawa 921, Japan TEL:+81-762-96-0111 FAX:+81-762-98-1139 ********** Local Arrangements ************ For additional information concerning registration, hotel reservation, and local arrangements, please contact: Haruo Yokota Local/Registration Chair of ISPAN'94 Graduate School of Information Science JAIST 15 Asahidai, Tatsunokuchi, ISHIKAWA 932-12, JAPAN TEL: +81-761-51-1271 FAX: +81-761-51-1149 e-mail: ispan94@jaist.ac.jp ****************************************************************** * Advanced Program of ISPAN'94 * ****************************************************************** December 13, 1994 17:00 - 19:00 Registration (International Hotel Kanazawa) December 14, 1994 8:00 - Registration 9:15 - 9:30 Opening Remarks 9:30 - 10:30 Invited Talk * Views of Mixed-Mode Computing and Network Evaluation Professor H.J. Siegel (Purdue University, U.S.A) 10:30 - 10:40 Break 10:40 - 12:10 Session A1 (Parallel Processing) * A Massively Parallel Implementation of Pattern Classifiers on SIMD and MIMD Architectures K.P. Lam (University of Kent, United Kingdom) * Texture Analysis for Image Processing on General-Purpose Parallel Machines L. Boroczky, P. Cremonesi, N.Seaubottlo (Politecnico di Milano, Italy) * Parallel Relational Database Algorithms Revisited for Range Declustered Data Sets E. Schikuta (University of Vienna, Austria) 10:40 - 12:10 Session B1 (Algorithm) * An Algorithm for Maintaining Consistent View of Processes in Distributed Systems D.V. Hung (The United Nations University, Macau) * Bounds on the VLSI Layout Complexity of Homogeneous Product Networks A. Fernandez, K.Efe (University of SW Louisiana, U.S.A.) * Integrated VLSI Layout Compaction and Wire Balancing on a Shared Memory Multiprocessor : Evaluation of a Parallel Algorithms R.P.Chalasani, K.Thulasiraman, M.A.Comeau (Concordia University, Canada) 12:10 - 13:10 Lunch 13:10 - 15:10 Session A2 (Network) * Cube-Connected Modules: A Family of Cubic Networks G.H. Chen, H.L. Huang (National Taiwan University, Republic of China) * Building a Better Butterfly: The Multiplexed Metabutterfly F.T. Chong, E.A. Brewer, F.T. Leighton, T.F. Knight,Jr. (MIT, U.S.A.) * Recursive Circulant: A New Topology for Multicomputer Networks J.H. Park, K.Y. Chwa (KAIST, Korea) * Performance of 4-Dimensional PANDORA Networks R. Holt, A.B. Ruighaver (University of Melbourne, Australia) 13:10 - 15:10 Session B2 (Graph Theory) * Parallel Maximal Cliques Algorithms for Interval Graphs with Applications C.S. Wang, R.S. Chang (National Taiwan Institute of Technology, Republic of China) * Parallel Connectivity Algorithms on Permutation Graphs Y.W. Chen, S.J. Horng, T.W. Kao, H.R. Tsai, S.S.Tsai (National Taiwan Institute of Technology, Republic of China) * Parallel Graph Isomorphism Detection with Identification Matrices L. Chen (Fundamental Research Laboratory, U.S.A.) * Undirected Circulant Graphs F.P. Muga II (Ateneo de Manila University, Philippines) 15:10 - 15:20 Break 15:20 - 17:20 Session A3 (Architecture) * Processing Nested Loop Structure with Data-Flow Dependence on a CAM-Based Processor HAPP K.M. Lu, K. Tamaru (Kyoto University, Japan) * Software Pipelining for Jetpipeline Architecture M. Katahira, T. Sasaki, H. Shen, H. Kobayashi, T. Nakamura (Tohoku University, Japan) * Message-Based Efficient Remote Memory Access on a Highly Parallel Computer EM-X Y. Kodama, H. Sakane, M. Sato, S. Sakai, Y. Yamaguchi (Real World Computing Partnership, Japan) * Combining Message Switching with Circuit Switching in the Interconnection Cached Multiprocessor Network V. Gupta, E. Schenfeld (NEC Research Institute Inc., U.S.A.) 15:20 - 17:20 Session B3 (Algorithm) * An O(logN loglogN) Time RMESH Algorithm for the Simple Polygon Visibility Problem S.R. Kim, K. Park, Y.K.Cho (Seoul National University, Korea) * A Shortest Path Algorithm for Banded Matrices by a Mesh Connection without Processor Penalty A. Mei, Y. Igarashi (Gunma University, Japan) * Optimal Parallel Algorithm for Edge-Coloring Partial k-Trees with Bounded Degrees X. Zhou, T. Nishizeki (Tohoku University, Japan) * An Efficient Algorithm for Solving the Token Distribution Problem on k-ary d-cube Networks C.G. Diderich, M. Gengler, S.Ubeda (Swiss Federal Institute of Technology, Lausanne, Switerland) 18:30 - Reception December 15, 1994 9:00 - 10:00 Invited Talk * NCIC's Research and Development in Parallel Processing Professor G. Li (NCIC, China) 10:00 - 10:10 Break 10:10 - 12:10 Session A4 (Fault Tolerance) * Advanced Fault Tolerant Routing in Hypercubes Q.P. Gu, S. Peng (The University of Aizu, Japan) * Contention Sensitive Fault-Tolerant Routing Algorithms for Hypercubes R. Srinivasan, V. Chaudhary, S.M. Mahmud (Wayne State University, U.S.A.) * Cost-Effective Global Fault-Tolerant Multiprocessor C.S. Yang, S.Y. Wu (National Sun Yat-Sen University, Republic of China) * Adaptive Fault-Tolerant Wormhole Routing Algorithms with Low Virtual Channel Requirements S. Chalasani, R.V. Boppana (University of Wisconsin-Madison, U.S.A.) 10:40 - 12:10 Session B4 (Routing) * Gossiping on Mesh-Bus Computers by Packets S. Fujita, M. Yamashita, T. Ae (Hiroshima University, Japan) * Optimal Total Exchange in Linear Arrays and Rings V.V. Dimakopoulos, N.J. Dimopoulos (University of Victoria, Canada) * Quicksort and Permutation Rouing on the Hypercube and de Bruijn Networks D.S.L. Wei (The University of Aizu, Japan) * Architectural Issues in Designing Heterogeneous Parallel Systems with Passive Star-Coupled Optical Interconnection R. Prakash, D.K. Panda (The Ohio State University, U.S.A.) 12:10 - 13:10 Lunch 13:10 - 14:10 Invited Talk * Massively Parallel Processing Systems Projects as a Priority Research Area of Ministry of Education Professor H. Tanaka (The University of Tokyo, Japan) 14:10 - 14:20 Break 14:20 - 16:30 Session A5 (Panel Session) * Announcement of Poster Papers * Massively Parallel Computation Towards the 21st Century H.J.Siegel(Purdue Univ.), G.Li(NCIC), H.Tanaka(Tokyo Univ.), R.Lee(Providence Univ.), T.F.Knight(MIT), S.Horiguchi(JAIST) 14:20 - 16:00 Session B5 (Memory Architecture) * Announcement of Poster Papers * An Interprocessor Memory Access Arbitrating Scheme for the S-3800 Vector Supercomputer T. Sakakibara, K. Kitai, T. Isobe, S. Yazawa, T. Tanaka, Y. Tamaki, Y. Inagami (Hitachi Ltd., Japan) * Efficient Implementation Techniques for Vector Memory Systems T. Chiueh, M. Verma, S. Padubidri (SUNY-Stony Brook, U.S.A.) 16:30 - 16:40 Break 16:40 - 18:30 Poster Session * List of Poster Papers December 16, 1994 9:00 - 10:00 Invited Talk * A Parallel Algorithm for the Single Step Searching Problem Dr. R.C.T. Lee (Providence University, Republic of China) 10:00 - 10:10 Break 10:10 - 12:10 Session A6 (Network) * Efficient Algorithms for Conservative Parallel Simulation of Interconnection Networks Y.M. Teo ,S.C. Tay (National University of Singapore, Singapore) * Performance Evaluation of High-Speed Self-Token Ring LAN K. Tanno, A. Koyama, S. Mirza, T. Takeda, S. Noguchi (Yamagata University, Japan) * A Performance Evaluation Procedure for a Class of Growable ATM Switches Z. Tsai, K. Yu, F. Lai (National Taiwan University, Republic of China) * Message Transfer Algorithms on the Recursive Diagonal Torus Y. Yang, H. Amano (Keio University, Japan) 10:10 - 12:10 Session B6 (Parallelization) * Cenju-3 Parallel Computer and its Application to CFD K. Muramatsu, S. Doi, T. Washio, T. Nakata (NEC, Japan) * Distributed Validation of Massively Parallel Machines C. Aktouf, O. Benkahla, C. Robach (LGI-IMAG, France) * Compiler-Chosen Operator Granularity in a Functionally-Programmed Tagged Token Architecture G. Jennings (Lulea Institute of Technology, Sweden) * A Logic Semantics for a Class of Nondeterministic Concurrent Constraint Logic Programs H.F. Leung, B.M. Tong (The Chinese University of Hong Kong, Hong Kong) 12:10 - 13:10 Lunch 13:10 - 14:10 Invited Talk * Simple Source Responsible Protocols for Fault Tolerant Interconnection Professor Thomas F. Knight, Jr. (MIT, U.S.A.) 14:10 - 14:20 Break 14:20 - 15:50 Session A7 (Array) * Matrix Multiplication on the MasPar Using Distance Insensitive Communication Schemes X. Sun, F. Lombardi (Texas A&M University, U.S.A.) * Mathematic-Physical Engine:Parallel Processing for Modeling and Simulation of Physical Phenomena V.K. Jain, A.D. Snider (University of South Florida, U.S.A.) * A Systolic Array Implementation of Common Factor Algorithm to Compute DFT S. He, M. Torkelson (Lund University, Sweden) 14:20 - 15:50 Session B7 (Load Balancing) * A Detailed Analysis of Random Polling Dynamic Load Balancing P. Sanders (Universitat Karlsruhe, Germany) * Increase Analysis in the Total Execution Time of a Parallel Program D. Li, H. Takagi, N. Ishii (Nagoya Institute of Technology, Japan) * A Greedy Task Clustering Heuristic that is Provably Good M.A. Palis, J.C. Liou, D.S.L. Wei (New Jersey Institute of Technology, U.S.A.) 15:50 - 16:00 Break 16:00 - 17:30 Session A8 (Scheduling) * Strategy and Simulation of Adaptive RID for Distributed Dynamic Load Balancing in Parallel Systems C. Lin, S. Li (Tsinghua University, China) * A Novel Hypercube with Lower Latency A. Ahmed (University of Massachusetts Dartmouth, U.S.A.) * Organization of Parallel Virtual Machine V. Beletsky, T. Popova, A. Chemeris (Academy of Sciences of the Ukraine, the Ukraine) 16:00 - 17:30 Session B8 (JUMP-1 Project) * Overview of the JUMP-1, an MPP Prototype for General-Purpose Parallel Computers K. Hiraki (The University of Tokyo, Japan) * Comprehensive Operating System for Highly Parallel Machine N. Saito (Keio University, Japan) * Research on Programming Languages for Massively Parallel Processing M. Amamiya (Kyushu University, Japan) ******************************************** * Poster Session * ******************************************** Algorithm * Radix-4 Parallel FFT Algorithms on the MasPar$^{tm}$ with an Eight-Neighbor Processor Array, Toshihiro Taketa, Kuninobu Tanno, Susumu Horiguchi, Yamagata University, Japan * A Reliable Sorting Algorithm on Hypercube Multicomputers, Yuh-Shyan Chen, Jang-Ping Sheu, National Central University, Taiwan * Ranking, Unranking, and Parallel Enumerating of Shortest Disjoint Paths on Hypercube, B. Y. Wu, C. Y. Tang, National Tsing Hua University, Taiwan * A Parallel Algorithm for the Cardinality Graphic Matroid Intersection Problem, Ying Xu, Harold N. Gabow, Oak Ridge National Labratory, U.S.A * Parallel Ray Casting Algorithm, Chong Man Nang, Katherine Mu Qing, David Flyn, Lee Yong Tsui, Seah Hock Soon, Daniel Tan T.H., Peter Mack, Nanyang Technological University, Singapore * Several Distributed Algorithms for Runtime Construction of Arbitrary-Length Linear Arrays and Rings in the RCH System, Issac Yi-Yuan Lee, Sheng-De Wang, National Taiwan University, Taiwan * Parallel Algorithm for a Domination Problem in Weighted Permutation Graphs, Haklin Kimm, University of Tennessee at Martin, U.S.A. * A Parallel Algorithm to Solve Block Tridiagonal Linear Systems, Takashi Naritomi, Hirotomo Aso, Tohoku University, Japan * A Practical View on Parallelisation of Genetic Algorithm, J. M\"{a}ntykoski, J. Vuori, J. Skytt\"{a}, Helsinki University of Technology, Finland Architecture * An Optimal Mapping of a Global Array to Hierarchical Memory Systems with Three Levels, Xiaojie Li, Ken'ichi Harada, Keio University,Japan * Decrease of the Effect of Harzard Due to the Conditional Branch by Use of Micro Instruction, Masato Abe, Kouki Okabe, Yoshiaki Nemoto, Tohoku University, Japan * A Note on Spare Assignments for Mesh Arrays -Minimizations of Dangerous Processors-, Itsuo Takanami, Katsushi Inoue, Takahiro Watanabe, Iwate University, Japan * Optimal Task Allocation to Maximize Reliability of Parallel and Distributed Computer Systems, Chan-Ik Park, Seong-Hwan Lee, POSTECH, Korea * Robust Checksum Tests in Algorithm-Based Fault Tolerance on 2-D Processor Arrays, Dah-Yea D.Wei, Gi-Yong Song, Jung H. Kim, T.R.N. Rao, University of SW Louisiana, U.S.A. * A Performance Study of Hierarchical Bus-Based Distributed Shared-Memory Multiprocessor Systems, Wernhuar Tarng, Mingteh Chen, Tein-Hsiang Lin, National Hsin-Chu Thechers College, Taiwan * High-Speed Double Precision Computation of Nonlinear Funtions, V. K. Jain, L. Lin, University of South Florida, U.S.A. * Intelligent Code Migration of Sychronization Operation for Performance Enhancement on a Multiprocessor, Rong-Yuh Hwang, Feipei Lai, National Taiwan University, Taiwan * Design of a Hardware Router for Recursive Circulant Multicomputers, Jong-Min Lee, Ji-Yun Kim, Jai-Hoon Chung, Bo Seob Kwon, Hyunsoo Yoon, Seung Ryoul Maeng,KAIST, Korea * A Note on a Single Machine Generalized Due Dates Scheduling Problems, C. S. Wong, Monique Yan, San Francisco University, U.S.A * Modular Fault-Tolerant Design and a Reliability Allocation Algorithm for Mission-Critical Multiprocessor Architectures, Ratan K. Guha, Debasish (Dev) Roy, University of Central Florida, U.S.A * AP1000+: Architectural Support for Parallelizing Compilers and Parallel Programs, Kenichi Hayashi, Tunehisa Doi, Takeshi Horie, Yoichi Koyanagi, Osamu Shiraki, Nobutaka Imamura, Toshiyuki Shimizu, Hiroaki Ishihata, Tatsuya Shindo, Fujitsu Laboratories Ltd.,Japan * (M$\pi$)$^2$: A Hierarchical Parallel Processing System for a Global Illumination Model, Hiroaki Kobayashi, Hitoshi Yamauchi, Yuichiro Toh, Tadao Nakamura, Tohoku University, Japan * VPP Fortran and Parallel Programming on the VPP500 Supercomputer, Hidetoshi Iwashita, Shin Okada, Makoto Nakanishi, Tatsuya Shindo, Hiroshi Nagakura, Fujitsu Laboratories Ltd., Japan * Integrated Memory Array Processor: IMAP - A 3.84 GIPS SIMD Processing LSI -, Nobuyuki Yamashita, Yoshihiro Fujita, Tohru Kimura, Kazuyuki Nakamura, Shin'ichiro Okazaki, NEC Corporation, Japan * Iterative Improvement on Load Balancing Property of Array Reconfiguration, Ting-Ting Y.Lin, Li-Cheng Tai, University of California at San Diego, U.S.A Network * Latency Analysis of Multicast Communication, Akihiro Fujii, Yoshiaki Nemoto, Tohoku University, Japan * Highly Parallel Computation Model for Setting Rearrangeable Type Interconnection Network, Issam A.Hamid, Tohoku University of Art \& Design, Japan * Relationships between the Networks, Masaru Takesue, Hosei Univeristy, Japan * Fault Tolerant Routing for Arrangement Graphs, Peter M.Yamakawa, Hiroyuki Ebara, Hideo Nakano, Osaka University, Japan * Virtual Tree: A Remedy for Hot Spot Contention in the Data Diffusion Machine, Hitoshi Oi, Akiyoshi Wakatani,University of Bristol, U.K. * Some Characteristics of Q-Stars, Chin-Tsai Lin, Ferng-Ching Lin,National Taiwan University, Taiwan * Improving Dependability of Network Management Systems, Elias Proc\'{o}pio Duarte Jr., Glenn Mansfield, Masatoshi Miyazaki, Shoichi Noguchi, Tohoku University, Japan * Varietal Hypercube - A New Interconnection Network Topology for Large Scale Multicomputer, Shou-Yi Cheng, Jen-Hui Chuang, National Chiao Tung University, Taiwan * A Fault-Tolerant Cost-effective Combining Structure for Multistage Interconnection Network, Jen-Hui Chuang, Chien-Chou Lin, National Chiao Tung University, Taiwan ************************************************************ * ISPAN'94 Advance Registration by Oct. 30, 1994 * ************************************************************ FAX: +81-761-51-1149 Dr. Haruo Yokota ISPAN'94 Registration Chair JAIST Asahidai 15, Tatsunokuchi, ISHIKAWA, 923-12, JAPAN Dear ISPAN'94 Registration Chair, I would like to make a registration to ISPAN'94, Dec.14-16, 1994 in Kanazawa. I will send the registration fee to ISPAN'94 by Bank Transfer on date of remittance as below. Signature: Date: / /94 ----------------------------------------------------------- ----------------------------------------------------------- Last Name/ Family Name First Name ----------------------------------------------------------- Paper number: ----------------------------------------------------------- Title: ----------------------------------------------------------- Name: ----------------------------------------------------------- Affiliation: ----------------------------------------------------------- Address: ----------------------------------------------------------- City Country Post Code ----------------------------------------------------------- Telephone: Facsimile: ----------------------------------------------------------- e-mail address: ----------------------------------------------------------- Member Ship Number IEEE ----------------------------------------------------------- Bank Name: ----------------------------------------------------------- Date of remittance: / /94 ----------------------------------------------------------- Member 25,000yen Non member 30,000yen Student 10,000yen ----------------------------------------------------------- by October 30, 1994 *********** BANK (Telegraph) Transfer ************ Bank Name: Hokkoku Bank Ltd., Tatsunokuchi Branch Address : 104 Tatsunokuchi, ISHIKAWA 923-12, JAPAN Account No.: 080140 Account name: ISPAN'94 *************************************************** Susumu Horiguchi ISPAN'94 Program Chair ISAPN'94 Executive Committee Chair