<link rel="stylesheet" href="styles.cf390c6bfbe7555f.css">

學術出版;;Publications

Permanent URI for this communityhdl:11536/1

收集所有交通大學研究人員與學生個人或團體所發表之各項學術著作，涵蓋期刊論文、教師專書、學位論文等項。;;Collections of Publications of NCTU Researchers and Students Like Journal Papers and Thesis.

Browse

🏛️國立陽明交通大學機構典藏

Access type: Metadata onlySubject: search.filters.subject.Algorithms

Search Results

Now showing 1 - 10 of 12
  • Thumbnail Image
    Item type:Item,
    Hybrid Dandelion: Visual Aesthetics of Performance Through Bionic Mechanism with Data from Biometric Facial Recognition
    (2019-01-01)
    Huang, Scottie Chih-Chieh
    ;
    Hsiao, Chung-Yun
    ;
    資訊工程學系
    ;
    Department of Computer Science
    Hybrid Dandelion is an interactive real-time animation art installation, used bionic mechanisms of algorithmic design to study generative rules for mimic biological form. It provides an approach to combine the algorithmic data structures from distributed computing, fractal tree, and L-system for investigate growth dandelion-like morphology. This work creates an interaction scenario with using facial recognition to scan audience's biometrics as means decoding your genetic data, and then inserting (the trait) into the dandelion model for modifying its indeed generative rules as like metaphor hybrid genetically modified task. It allows the audience to experience their unique data-driven artificial life form - dandelion as embodied and possessed through their facial features, heartbeat signal, and emotion expression in artistic expression.
  • Thumbnail Image
    Item type:Item,
    Scan-Cell Reordering for Minimizing Scan-Shift Power Based on Nonspecified Test Cubes
    (2010-11-01)
    Wu, Yu-Ze
    ;
    Chao, Mango C. -T.
    ;
    電子工程學系及電子研究所
    ;
    Department of Electronics Engineering and Institute of Electronics
    This article presents several scan-cell reordering techniques to reduce the signal transitions during the test mode while preserving the don't-care bits in the test patterns for a later optimization. Combined with a pattern-filling technique, the proposed scan-cell reordering techniques can utilize both high response correlations and pattern correlations to simultaneously minimize scan-out and scan-in transitions. Those scan-shift transitions can be further reduced by selectively using the inverse connections between scan cells. In addition, the trade-off between routing overhead and power consumption can also be controlled by the proposed scan-cell reordering techniques. A series of experiments are conducted to demonstrate the effectiveness of each of the proposed techniques individually.
  • Thumbnail Image
    Item type:Item,
    Vector-Aware Register Allocation for GPU Shader Processors
    (2015)
    You, Yi-Ping
    ;
    Chen, Szu-Chieh
    ;
    資訊工程學系
    ;
    Department of Computer Science
    Graphics processing units (GPUs) are now widely used in embedded systems for manipulating computer graphics and even for general-purpose computation. However, many embedded systems have to manage highly restricted hardware resources in order to achieve high performance or energy efficiency. The number of registers is one of the common limiting factors in an embedded GPU design. Programs that run with a low number of registers may suffer from high register pressure if register allocation is not properly designed, especially on a GPU in which a register is divided into four elements and each element can be accessed separately, because allocating a register for a vector-type variable that does not contain values in all elements wastes register spaces. In this paper we present a vector-aware register allocation framework to improve register utilization on shader architectures. The framework involves two major components: (1) element-based register allocation that allocates registers based on the element requirement of variables and (2) register packing that rearranges elements of registers in order to increase the number of contiguous free elements, thereby keeping more live variables in registers. Experimental results on a cycle-approximate simulator showed that the proposed framework decreased 92% of register spills in total and made 91.7% of 14 common shader programs spill-free. These results indicate an opportunity for energy management of the space that is used for storing spilled variables, with the framework improving the performance by a geometric mean of 8.3%, 16.3%, and 29.2% for general shader processors in which variables are spilled to memory with 5-, 10-, and 20-cycle access latencies, respectively. Furthermore, the reduction in the register requirement of programs enabled another 11 programs with high register pressure to be runnable on a lightweight GPU.
  • Thumbnail Image
    Item type:Item,
    An EDA Framework for Large Scale Hybrid Neuromorphic Computing Systems
    (2015)
    Wen, Wei
    ;
    Wu, Chi-Ruo
    ;
    Hu, Xiaofang
    ;
    Liu, Beiye
    ;
    Ho, Tsung-Yi
    In implementations of neuromorphic computing systems (NCS), memristor and its crossbar topology have been widely used to realize fully connected neural networks. However, many neural networks utilized in real applications often have a sparse connectivity, which is hard to be efficiently mapped to a crossbar structure. Moreover, the scale of the neural networks is normally much larger than that can be offered by the latest integration technology of memristor crossbars. In this work, we propose AutoNCS - an EDA framework that can automate the NCS designs that combine memristor crossbars and discrete synapse modules. The connections of the neural networks are clustered to improve the utilization of the memristor elements in crossbar structures by taking into account the physical design cost of the NCS. Our results show that AutoNCS can substantially enhance the utilization efficiency of memristor crossbars while reducing the wirelength, area and delay of the physical designs of the NCS.
  • Thumbnail Image
    Item type:Item,
    Scalable Global Power Management Policy Based on Combinatorial Optimization for Multiprocessors
    (2015-12-01)
    Pan, Gung-Yu
    ;
    Yang, Jed
    ;
    Jou, Jing-Yang
    ;
    Lai, Bo-Cheng Charles
    ;
    交大名義發表
    Multiprocessors have become the main architecture trend in modern systems due to the superior performance; nevertheless, the power consumption remains a critical challenge. Global power management (GPM) aims at dynamically finding the power state combination that satisfies the power budget constraint while maximizing the overall performance (or vice versa). Due to the increasing number of cores in a multiprocessor system, the scalability of GPM policies has become critical when searching satisfactory state combinations within acceptable time. This article proposes a highly scalable policy based on combinatorial optimization with theoretical proofs, whereas previous works take exhaustive search or heuristic methods. The proposed policy first applies an optimum algorithm to construct a state combination table in pseudo polynomial time using dynamic programming. Then, the state combination is assigned to cores with minimum transition cost in linear time by mapping to the network flow problem. Simulation results show that the proposed policy achieves better system performance for any given power budget when compared to the state-of-the-art heuristic. Furthermore, the proposed policy demonstrates its prominent scalability with 125 times faster policy runtime for 512 cores.
  • Thumbnail Image
    Item type:Item,
    Significant Correlation Pattern Mining in Smart Homes
    (2015-05-01)
    Chen, Yi-Cheng
    ;
    Peng, Wen-Chih
    ;
    Huang, Jiun-Long
    ;
    Lee, Wang-Chien
    ;
    資訊工程學系
    Owing to the great advent of sensor technology, the usage data of appliances in a house can be logged and collected easily today. However, it is a challenge for the residents to visualize how these appliances are used. Thus, mining algorithms are much needed to discover appliance usage patterns. Most previous studies on usage pattern discovery are mainly focused on analyzing the patterns of single appliance rather than mining the usage correlation among appliances. In this article, a novel algorithm, namely Correlation Pattern Miner (CoPMiner), is developed to capture the usage patterns and correlations among appliances probabilistically. CoPMiner also employs four pruning techniques and a statistical model to reduce the search space and filter out insignificant patterns, respectively. Furthermore, the proposed algorithm is applied on a real-world dataset to show the practicability of correlation pattern mining.
  • Thumbnail Image
    Item type:Item,
    開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型---含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
    (2008)
    盧錦隆
    ;
    LU CHIN LUNG
    ;
    國立交通大學生物科技學系(所)
    幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。
  • Thumbnail Image
    Item type:Item,
    開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型-含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
    (2009)
    盧錦隆
    ;
    LU CHIN LUNG
    ;
    國立交通大學生物科技學系(所)
    幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。
  • Thumbnail Image
    Item type:Item,
    開發生物資訊新工具去探索RNA病毒序列、結構、功能與演化---以流感病毒與腸病毒為應用模型---含有假結的RNA二級結構預測與其在偵測程序性核糖體移碼基因的應用
    (2010)
    盧錦隆
    ;
    LU CHIN LUNG
    ;
    國立交通大學生物科技學系（所）
    幾乎在所有自然存在的RNA結構中皆可發現所謂的假結(Pseudoknot)，其在各種的生物反應中如RNA的複製、轉錄與轉譯等等扮演著非常重要的角色。例如他們可以擔任程序性核糖體移碼(Programmed Ribosomal Frameshifting)的刺激物。所謂的程序性核糖體移碼乃是一種重新編碼(Recoding)的機制，而且經常在很多的RNA病毒(如SARS冠狀病毒)上被發現。病毒藉由這個機制，可讓正在進行轉譯的核糖體在某一個特定的位置上從原來的讀碼框(Open Reading Frame)切換到新的讀碼框(如-1或+1讀碼框，其中切換到-1讀碼框者佔大多數)，結果產生另一個新的蛋白質，其不同於原來不發生移碼時所產生的蛋白質。據文獻的報導對於利用此機制的病毒，即便很小地改變其移碼效率就可以抑制其繁殖，這意味著程序性核糖體移碼位置可充當抗病毒藥劑的標的。目前為止，被發現的RNA假結大多數是所謂的H型結構，基本上它是一個髮夾(Hairpin)的結構，其中在髮夾迴圈(Hairpin Loop)的核苷酸會和髮夾外面的核苷酸配對並形成一個靠近或非常靠近髮夾的螺旋主幹(Helical Stem)。事實上，較複雜的H型假結也曾被發現，比如說在SARS冠狀病毒上擔任程序性核糖體移碼刺激物的假結就比平常的H型假結多出一個主幹出來。因此，預測這些H型甚至更複雜的假結結構將有助於我們對RNA結構與其功能的了解。在一般標準的熱動力模型(Thermodynamic Model)上，不含假結的最小自由能量(Minimum Free Energy)的RNA二級結構是可以在多項式時間(Polynomial Time)內被計算出來。然而，要去計算含有假結的最小自由能量的RNA二級結構便變成了一件非常困難的事情，因為它已被證明出是件NP-hard的問題。目前已有許多的多項式時間的演算法被設計出來可以用來計算出含有特定型態的假結(如H型假結)的最小自由能量的RNA二級結構。然而，這些演算法的時間與空間(即記憶體)複雜度仍非常的高，故尚不能實際地被拿來處理較長甚至大型的RNA序列。除此之外，這些演算法也不見得能夠偵測出在一條長的RNA序列中所含的H型假結。過去，我們已經提出一個啟發式(Heuristic)的方法可以改進這些演算法去預測H型的假結，同時也把它應用到-1和+1型程序性核糖體移碼的偵測。然而，這個啟發式方法仍有很多可以再被改進與增強的地方，比如說降低其執行時間與所需記憶體的複雜度、增強使其能處理大型序列的能力、改進其預測的準確度、增強使其能夠去預測較複雜的RNA假結結構與偵測其它型態的程序性核糖體移碼(如-2與+2型的程序性核糖體移碼)。在這個子計劃中，我們主要的目的是利用比較基因體學、結構生物資訊學與功能生物資訊學的方法去發展出新的演算法與啟發式方法來進行上述的改良與增強，同時也將去發展出含有假結的RNA二級結構資料庫與程序性核糖體移碼的資料庫。因此，為了完成這些目標我們需要和其他的子計劃成員一起合作，因為他們能夠提供給我們一些在他們研究領域上的專業知識與技術，以及一些在他們子計劃中預期能夠發展出來的相關程式。同時，我們子計劃發展出來的程式與資料庫也能夠幫助其他子計劃成員去研究RNA病毒，例如流行感冒病毒與腸病毒等，並進一步地去探討這些RNA病毒的序列、結構、功能與演化的關係。
  • Thumbnail Image
    Item type:Item,
    計算幾何學中最短和最長對角線問題之研究
    (1994)
    陳秋媛
    ;
    CHEN CHIUYUAN
    ;
    國立交通大學應用數學系
    1978年,科學家Shamos提出了一個新的研究領域 :計算幾何學.這是一個結合計算機科學與幾何 學的新領域,它的目的在探討如何用計算機來 迅速地求得幾何學問題的解,例如:找包含n個給 定的點的Convex hull,找兩個多邊形的交集,以及 求兩個給定的點間的最短路徑...等問題.在這 個計畫中,我們將研究計算幾何學中的"最短對 角線"和"最長對角線"問題.我們的目的是希望 能設計出很快速的"演算法",來求出一個給定的 多邊形的最短對角線和最長對角線.