[특허]Method and apparatus for optimizing cost-based heuristic instruction scheduling

Method and apparatus for optimizing cost-based heuristic instruction scheduling 원문보기

IPC분류정보
국가/구분	United States(US) Patent 등록
국제특허분류(IPC7판)	G06F-009/38
출원번호	US-0088418 (1993-07-07)
발명자 / 주소	Tarsy Gregory (Scotts Valley CA) Woodard Michael J. (Fremont CA)
출원인 / 주소	Sun Microsystems, Inc. (Mountain View CA 02)
인용정보	피인용 횟수 : 33 인용 특허 : 0

초록 ▼

A method and apparatus for optimizing cost-based heuristic instruction scheduling for a pipelined processor is disclosed which has particular application to compile time instruction scheduling after code generation. Instruction scheduling is optimized by determining the optimal weights to be used by an apparatus for cost based heuristic instruction scheduling for a particular pipelined processor. The optimal weights are determined based on the lowest of the lowest costs incurred by different collections of interrelated weight sets. Each collection of interrelated weight sets comprises a randomly generated initial weight set and subsequent interrelated weight sets generated in a predetermined manner. The predetermined manner for generating subsequent weight sets facilitates rapid identification of the optimal weight set for a collection, and thereby rapid identification of the overall optimal weight set for the collections.

대표청구항 ▼

In a computer system comprising a pipelined processor for executing instructions of programs in a parallel and overlapping manner, and a compiler for compiling and generating said instructions, wherein said compiler has a scheduler for scheduling said instructions for execution on said pipelined processor, and said scheduler schedules said instructions using N weighted cost based heuristics, a method for empirically selecting a set of N weights for said scheduler to weigh said N cost based heuristics, said method comprising the steps of: a) generating arbitrarily an initial trial set of N weights, initializing said scheduler with said arbitrarily generated initial trial set of N weights, generating a plurality of benchmark programs, compiling said benchmark programs using said compiler, accumulating scheduling costs determined by said scheduler for said benchmark programs, initializing a lowest accumulated scheduling cost of said benchmark programs to said accumulated scheduling cost, and selecting said initial trial set of N weights as the selected set of N weights for said scheduler; b) generating sequentially a first plurality of additional trial sets of N weights in a first manner, one trial set of N weights at a time, each of said first plurality of additional trial sets of N weights being generated by systematically varying the immediately preceding trial set of N weights along an orthogonal dimension of a weight space formed by the N weights, one orthogonal dimension at a time, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets of N weights in said first manner as soon as a new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the newly found lowest accumulated scheduling cost if a new lowest accumulated scheduling cost is found, and selecting the trial set of N weights that yields the new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if a new lowest accumulated scheduling cost is found; and c) generating sequentially a second plurality of additional trial sets of N weights in a second manner, one additional trial set of N weights at a time, each of said additional trial sets of N weights being generated under said second manner by systematically varying the immediately preceding trial set of N weights along the last orthogonal dimension with the last systematic variation made under said first manner, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets in said second manner as soon as no new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the last newly determined lowest accumulated scheduling cost if at least one newly determined lowest accumulated scheduling cost is found, and selecting the last trial set of N weights that yields the last new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if at least one newly determined lowest accumulated scheduling cost is found.

이 특허를 인용한 특허 (33)

Heidari, Ghobad; Chang, Kuor Hsin; Master, Paul L.; Hogenauer, Eugene B.; Scheuermann, Walter James, Communications module, device, and method for implementing a system acquisition function.
상세보기
Soltis, Jr.,Donald C.; Delano,Eric, Core parallel execution with different optimization characteristics to decrease dynamic execution path.
상세보기
Scheuermann, W. James; Hogenauer, Eugene B., Hardware task manager.
상세보기
Kojima Hirotsugu (Foster City CA) Sasaki Katsuro (Los Altos CA), High speed, reduced power memory system implemented according to access frequency.
상세보기
de Jong,Eduard K., Interleaved data and instruction streams for application program obfuscation.
상세보기
Long, Dean R. E., Interpreter optimization for native endianness.
상세보기
Sambhwani, Sharad; Heidari, Ghobad, Low I/O bandwidth method and system for implementing detection and identification of scrambling codes.
상세보기
Sambhwani, Sharad; Heidari, Ghobad, Low I/O bandwidth method and system for implementing detection and identification of scrambling codes.
상세보기
Blumenthal, Andreas; Luedde, Mirko; Manzke, Thomas; Mielenhausen, Bjoern; Swanepoel, Christiaan E., Measuring software system performance using benchmarks.
상세보기
Tirumalai Partha P. (Fremont CA), Method and apparatus for automatic selection of the load latency to be used in modulo scheduling in an optimizing compil.
상세보기
Smaalders Bart ; Clarke Kevin J., Method and apparatus for reordering components of computer programs.
상세보기
Arbabi Mansur (Montgomery County MD) Baniak Jonathan E. (Montgomery County MD), Method and apparatus for scheduling resources.
상세보기
Master, Paul L., Method and system for creating and programming an adaptive computing engine.
상세보기
Scheuermann, W. James, Method and system for reconfigurable channel coding.
상세보기
Scheuermann, W. James, Method and system for reconfigurable channel coding.
상세보기
Scheuermann, W. James, Method and system for reconfigurable channel coding.
상세보기
Scheuermann, W. James, Method and system for reconfigurable channel coding.
상세보기
Hill, Ralph D., Method for estimating cost when placing operations within a modulo scheduler when scheduling for processors with a large number of function units or reconfigurable data paths.
상세보기
Hill,Ralph D., Method for estimating cost when placing operations within a modulo scheduler when scheduling for processors with a large number of function units or reconfigurable data paths.
상세보기
Chen Chi-Chung K., Method for generating instructions for an object-oriented processor.
상세보기
Mitran, Marcel; Siu, Joran S. C.; Vasilevskiy, Alexander, Methods, systems, and computer products for evaluating robustness of a list scheduling framework.
상세보기
de Jong,Eduard K., Multiple instruction dispatch tables for application program obfuscation.
상세보기
de Jong,Eduard K., Non-linear execution of application program instructions for application program obfuscation.
상세보기
Rehg,James M.; Knobe,Kathleen, On-line scheduling of constrained dynamic applications for parallel targets.
상세보기
de Jong,Eduard K., Permutation of opcode values for application program obfuscation.
상세보기
Martin, Allan Russell, Pinning internal slack nodes to improve instruction scheduling.
상세보기
Martin,Allan Russell, Pinning internal slack nodes to improve instruction scheduling.
상세보기
Volkonsky, Vladimir Y.; Ostanevich, Alexander Y.; Sushentsov, Alexander L., Profile driven code motion and scheduling.
상세보기
Master, Paul L., Profiling of software and circuit designs utilizing data operation analyses.
상세보기
de Jong, Eduard K., Rendering and encryption engine for application program obfuscation.
상세보기
Master, Paul L.; Watson, John, System for adapting device standards after manufacture.
상세보기
Rehg,James M.; Knobe,Kathleen, System for computing the optimal static schedule using the stored task execution costs with recent schedule execution costs.
상세보기
Katragadda, Ramana; Spoltore, Paul; Howard, Ric, Task definition for specifying resource requirements.
상세보기

IPC	Description
A	생활필수품
A62	인명구조; 소방(사다리 E06C)
A62B	인명구조용의 기구, 장치 또는 방법(특히 의료용에 사용되는 밸브 A61M 39/00; 특히 물에서 쓰이는 인명구조 장치 또는 방법 B63C 9/00; 잠수장비 B63C 11/00; 특히 항공기에 쓰는 것, 예. 낙하산, 투출좌석 B64D; 특히 광산에서 쓰이는 구조장치 E21F 11/00)
A62B-1/08	.. 윈치 또는 풀리에 제동기구가 있는 것

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표IPC 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 공고번호, 공고일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표출원인, 출원인국적, 출원인주소, 발명자, 발명자E, 발명자코드, 발명자주소, 발명자 우편번호, 발명자국적, 대표IPC, IPC코드, 요약, 미국특허분류, 대리인주소, 대리인코드, 대리인(한글), 대리인(영문), 국제공개일자, 국제공개번호, 국제출원일자, 국제출원번호, 우선권, 우선권주장일, 우선권국가, 우선권출원번호, 원출원일자, 원출원번호, 지정국, Citing Patents, Cited Patents
저장형식	Text(ASCII format) Excel format PIAS분석(.xls)
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

Method and apparatus for optimizing cost-based heuristic instruction scheduling 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

이 특허를 인용한 특허 (33)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

Method and apparatus for optimizing cost-based heuristic instruction scheduling 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

이 특허를 인용한 특허 (33)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트